(CF1407C) Chocolate Bunny

发表于 分类于 ，

我的第一道交互题.md (

原题链接

思路:

结论:

证明：反证法：若 \(a>b\), 则 \(b\ mod\ a = b > a\ mod\ b\), 若 \(a=b\), 则 \(a\ mod\ b = b\ mod\ a = 0\)

通过该结论可以设计一个算法：令一个变量 \(mx\) 为当前的最大值所在下标， 对于每个下标 \(i\), 每次询问 ? mx i 和 ? i mx, 通过结论可以对 \(p_{mx}\) 与 \(p_i\) 比较， 并且能得到两个数中较小那个数的值，同时更新 mx. 最终只有 \(p_{mx}\) 没有得到，而它显然是最大的数 \(n\).

需要的询问次数为 2*(n-1) 次.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
const int Mn(10050);
int arr[Mn];    //即数组p
int ask(int x,int y) {
    printf("? %d %d\n",x,y);
    int ret;
    fflush(stdout);    //交互题要求
    scanf("%d",&ret);
    return ret;
}

int main() {
    int n;
    scanf("%d",&n);
    int mx(1);
    for(int i(2);i<=n;++i) {
        int a = ask(mx,i);
        int b = ask(i,mx);
        if(a>b) {    //a>b说明p_mx < p_i
            arr[mx] = a;
            mx = i;
        } else {
            arr[i] = b;
        }
    }
    arr[mx] = n;
    printf("!");    //输出结果
    for(int i(1);i<=n;++i) {
        printf(" %d",arr[i]);
    }
    printf("\n");
    return 0;
}