[Codeforces] CF1807E Interview

题目翻译

有 \(n\) 堆石头，其中 \(n-1\) 堆都只有重量为一克的石头，剩下一堆有则有一块有两克的石头和若干重量为一克的石头。

你的任务是在 \(30\) 次询问内推理出那一堆有重量为两克的石头是第几堆。

首先输入 \(n\)，接下来输入 \(n\) 个数 \(a_1,a_2\dots a_n\)，其中 \(a_i\) 表示第 \(i\) 堆有 \(a_i\) 块石头。

一共有 \(t\) 组数据。

每次询问你需要输出 ? 这个符号，然后输出 $k $ 及 \(p_1,p_2\dots p_k\)（用空格隔开），表示询问 \(p_1,p_2\dots p_k\) 这 \(k\) 堆石头的总重量，然后你需要输入一个数 \(x\) 表示你刚刚询问得到的答案。

思路

非常明显的二分题，每次二分一个区间\([l,mid]\)，然后输出进行check，直到发现那个违反规则的

规则是什么呢？很明显，加入我们check了\([l,r]\)，那他的返回值如果是\(a_l+a_{l+1}+...+a_r\)，那就是说这些堆中没有混入重量为\(2\)的石子

否则，就说明重量为\(2\)的石子就在这个区间内，继续check

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int a[Maxn];
int n;
bool check(int l,int r)
{
    int x,re=0;
    cout<<"? "<<r-l+1<<" ";
    for(int i=l;i<=r;i++) cout<<i<<" ";
    cout<<endl;
    cout.flush();
    cin>>x;
    for(int i=l;i<=r;i++) re+=a[i];
    return re==x;
}
int run()
{
    int l,r,mid;
    cin>>n;
    l=1,r=n;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(l,mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<"! "<<l<<endl;
    cout.flush();
    return 0;
}
int main()
{
    int t;
    cin>>t;
    while(t--) run();
    return 0;
}