【Gym 100685J】Just Another Disney Problem（交互/排序）

饶文津

发布于 2020-06-02 15:40:55

2740

发布于 2020-06-02 15:40:55

文章被收录于专栏：饶文津的专栏饶文津的专栏

第一次做交互题。

题意是有n个数(n<1000)，你通过问1 a b，后台返回你YES代表a<b，NO代表a>b。要你在10000次询问内给出一个符合的排列。n=1000来说，10000其实就是大约nlogn。

所以需要一个时间复杂度稳定为nlogn的排序，每次询问的结果对应cmp函数的返回值。然后顺便了解一下stable sort：

稳定排序，它的这个稳定，主要是两个相同的元素，它不会改变原来的相对位置。
它是怎么判断两个元素是否相同的呢？ cmp(x,y) ==0 && cmp(y,x)==0 时就是相同的，所以你cmp的返回值应该是x>y，不是x>=y，否则稳定排序就失去意义了。
另外，一般情况下它用归并排序，在空间不足的情况下，它采用的是merge_without_buffer函数，也就是就地排序，这时的复杂度就是O(n*logn*logn)了。

这题我们用它单纯的只是需要它的归并排序而已，并没有用到相对位置的稳定性。如果是sort，用的是快排，时间复杂度不是稳定的O(nlogn)，而归并排序是稳定的O(nlogn)。

#include<bits/stdc++.h>
using namespace std;
#define N 10005
int n;
int a[N];
char s[10];
int cmp(int a,int b){
    printf("1 %d %d\n",a,b);
    fflush(stdout);
    scanf("%s",s);
    return s[0]=='Y';
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)a[i]=i;
    stable_sort(a+1, a+1+n, cmp);
    for(int i = 0;i<=n;i++)
        printf("%d ", a[i]);
    printf("\n");
    fflush(stdout);
    return 0;
}

　　我们也可以用二分来做这题：

#include<cstdio>
#include<cstring>
#define N 10005
int n;
int a[N];
char s[10];
int main(){
    scanf("%d",&n);
    a[1]=1;
    for(int i=2;i<=n;i++){
        int l=1,r=i;//已经排好了前i-1个
        while(l<r){
            int m=(l+r)>>1;
            printf("1 %d %d\n",i,a[m]);
            fflush(stdout);
            scanf("%s",s);
            if(s[0]=='Y') r=m;
            else l=m+1;
        }
        for(int j=i;j>l;j--)
            a[j]=a[j-1];
        a[l]=i;
    }
    for(int i = 0;i<=n;i++)
        printf("%d ", a[i]);
    printf("\n");
    fflush(stdout);
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-07-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

buffer