“繁杂的代码分部调试，
琐碎的思路模拟样例。”【一方面可以检验思路的正确性，另一方面模拟的过程也正是算法执行的过程】
- 采用以0为起点的标号方式，以处理环形结构
- 考虑将题目抽象成数学函数
- 考虑询问点在环上的移动可能会导致距离和+2，+1，不变，-1，-2
- 考虑距离和的变化趋势（而不是绝对值）所能提供的信息
- 通过一组询问，将答案限定在某条链上（实现“断环为链”），再在这一条链上做进一步的处理
- partition_point函数：或许可以看作是升级版的upper_bound，如果要用C++20的ranges::iota_view，则该函数也要做对应的改变（不要忘记星号）
- 交互题：通过endl就可以避免用cout.flush()清空缓存区
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int n,ans[2];
int query(int x)
{
int d;
cout<<"?"<<" "<<x+1<<endl;
cin>>d;
return d;
}
void shuchu()
{
cout<<"!"<<" "<<ans[0]+1<<" "<<ans[1]+1<<endl;
}
void solve()
{
int x=query(0);
int y=query(n/2);
int v,p;
if(x<y)
{
v=x;
p=0;
}
else
{
v=y;
p=n/2;
}
int vl=query((p-1+n)%n);
int vr=query((p+1)%n);
if(vl==v&&vr==v)
{
auto check=[&v,&p](int x)
{
return query(p+x)==v;
};
ans[0]=p+(*ranges::partition_point(ranges::iota_view(0,n/2),check))-1;
}
else if(vl<v)
{
auto check=[&v,&p](int x)
{
return v-query((p-x+n)%n)>=2*x;
};
int d=*ranges::partition_point(ranges::iota_view(0,n/2),check)-1;
ans[0]=(p-d+n)%n;
v=v-2*d;
}
else
{
auto check=[&v,&p](int x)
{
return v-query((p+x)%n)>=2*x;
};
int d=*ranges::partition_point(ranges::iota_view(0,n/2),check)-1;
ans[0]=(p+d)%n;
v=v-2*d;
}
int opt=query((ans[0]-1+n)%n);
if(opt==v)
{
ans[1]=(ans[0]-v+n)%n;
}
else
{
ans[1]=(ans[0]+v)%n;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n;
solve();
shuchu();
}
return 0;
}