D. Finding Zero

题目描述：

交互题

有一个n个元素的数组a，0<=ai<=1e9,但有且仅有一个0，你可以进行2*n-2次如下询问：

• ? i j k，你会得到 max{a[i], a[j], a[k]} - min{a[i], a[j], a[k]}，也就是极差

让你确定0的位置，输出如下

• ! i j，如果a[i] == 0 || a[j] == 0则ac

思路：

观察一下最多询问次数2*n-2，可以发现几乎是两倍的数组长度，也就方法大概是扫两遍数组来解决

所以我们可以先假设 p1 = 1 p2 = 2,然后从3开始枚举p3，获得最大的一个极差，这个时候，将他的位置定为p3，

• 当1和2的位置上不是0和n-1时，那p3一定是0或者n-1,这是因为1和2的最大值和最小值都固定了，只有0或n-1才能让极差得到最大
• 当1和2的位置上都是0和n-1时，每次询问都只会得到n-1，这就一个判断条件，我们直接判掉输出即可

现在我们找到了一个极值，然后我们再固定p1，p3，从3开始枚举p2，找到最大值的位置，记录下来为p2,要注意，这个的位置的值不一定就是剩下的那个极值，只有当p1的位置不是极值时它才是，所以现在两个极值其实已经确定在p1, p2, p3里面了，我们只需要找到一个新的点，用这个新的点去检测，就可以得出答案

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, x;
int p1, p2, p3;
int a, b;

int query(int p1, int p2, int p3){
    cout << "? " << p1 << ' ' << p2 << ' ' << p3 << endl;
    cout.flush();
    cin >> x;
    return x;
}

void ans(int a, int b){
    if(a > b)swap(a, b);
    cout << "! " << a << ' ' << b << endl;
    cout.flush();
}

void work(){
    cin >> n;
    p1 = 1; p2 = 2;p3 = 3;
    int m = 0;
    bool flag = 0;
    for(int i = 3; i <= n; ++i){
        int d = query(p1, p2, i);
        if(d != n - 1){
            flag = 1;
        }
        if(d > m){
            p3 = i;
            m = d;
        }
    }
    if(!flag){
        ans(1, 2);
        return;
    }
    for(int i = 3; i <= n; ++i){
        if(i == p3)continue;
        int d = query(p1, i, p3);
        if(d >= m){
            p2 = i;
            m = d;
        }
    }
    int p = 1;
    for(int i = 1; i <= n; ++i){
        if(i != p1 && i != p2 && i != p3){
            p = i;
            break;
        }
    }
    if(query(p2, p3, p) == m)ans(p2, p3);
    else if(query(p1, p3, p) == m)ans(p1, p3);
    else ans(p1, p2);
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}