题解：CF1270D Strange Device

题解：CF1270D Strange Device

解题思路

做法与 n 完全无关。只要询问前 k + 1 个数 k + 1 次，使每次询问的元素个数为 k 且每次询问不相同。

此时有两种可能，如果去除的数在前 m 小，则返回一个更大的数，否则返回一个较小的数。

因为是去除恰好一个数，所以会出现恰好两种回答。答案就是所有询问出现的较大的回答的个数。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n , k , pos , x , a[505] , ans;
int main()
{
    cin >> n >> k;
    for(int i = 1 ; i <= k + 1 ; i++)
    {
        cout << "? ";
        for(int j = 1 ; j <= k + 1 ; j++)
        {
            if(j != i)
            {
                cout << j << ' ';
            }
        }
        cout << endl;
        cin >> pos >> x;
        a[i] = x;
    }
    sort(a + 1 , a + 1 + k + 1);
    for(int i = 1 ; i <= k + 1 ; i++)
    {
        if(a[i] != a[1])
        {
            ans++;
        }
    }
    cout << "! " << ans << endl;
    return 0; 
}