題目鏈接：點擊查看

題目大意：規(guī)定一個含有n個元素的數(shù)組a，每個元素互不相等，但是全部未知，現(xiàn)在給出一臺機器，這臺機器有兩個參數(shù)，分別是k和m，其意義是每次可以詢問k個下標(biāo)，機器將給出k個下標(biāo)中第m大的下標(biāo)及其數(shù)值，現(xiàn)在k已知，要求在不超過n次詢問的情況下確定出m的大小

題目分析：看到這個題目給出的數(shù)據(jù)范圍是1<=m<=k<n，我第一反應(yīng)就是n其實沒有什么用，關(guān)鍵在于k，為了確定m，我們可以隨意取k+1個固定的數(shù)，每次可以刪除掉其中的一個，這樣對于剩下的k個數(shù)進行不同組合應(yīng)該是可以確定出m的，為了方便我們直接取前k+1個數(shù)來進行操作就好了，后來我想了想可不可以二分呢，大體思路就是先求出來1~k中第m大的數(shù)，然后二分亂搞，后來也不知道怎么還讓我亂搞過去了六組測試點，但突然一下子回過神來發(fā)現(xiàn)這個題目并不能二分，仔細(xì)想了一下我二分的其實是下標(biāo)，本來一開始是想二分m的，但是m是不能二分得到的，于是趕快轉(zhuǎn)換思路

好在一開始的方向沒有錯，就是在前k+1個數(shù)中，每次刪掉一個數(shù)形成k+1種不同的組合，接著向下該怎么想呢？其實可以將全部情況大致分為下列兩種來思考：

m<=k/2

m>k/2

為什么這樣想呢，首先我們籠統(tǒng)的分析一下，若刪掉前k+1中的某個數(shù)x，對機器造成的影響會是什么：

如果x在前k+1個數(shù)中的大小大于m，那么機器返回的答案一定是第m大的數(shù)的相關(guān)數(shù)據(jù)

如果x在前k+1個數(shù)中的大小小于等于m，那么機器返回的答案一定是第m+1大的數(shù)的相關(guān)數(shù)據(jù)

仔細(xì)斟酌一下上面兩句話，我們可以發(fā)現(xiàn)，如果以ans1表示第m大的數(shù)出現(xiàn)的次數(shù)，用ans2表示第m+1大的數(shù)出現(xiàn)的次數(shù)，那么答案一定是ans2，且ans1+ans2=k+1

如此一來我們只需要記錄一下第m+1大的數(shù)出現(xiàn)的次數(shù)就能直接求出答案了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=50;map<int,int>mp;int n,k;void print(int x) {printf("?");for(int i=1;i<x;i++)printf(" %d",i);for(int i=x+1;i<=k+1;i++)printf(" %d",i);printf("\n");fflush(stdout); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d",&n,&k);for(int i=1;i<=k+1;i++){print(i);int pos,val;scanf("%d%d",&pos,&val);mp[val]++;}printf("! %d\n",mp.rbegin()->second);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1270D Strange Device(思维+构造)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。