P8320 『JROI-4』Sunset 题解

MoSalah · 2022-05-02 22:53:36 · 题解

题意

这是一道交互题

首先，在这里感谢出题人让我知道了怎么写交互题。

在 5500 次询问内，你要求出最初的 a 数组。

询问方式有三种：

返回的数值 x 就是 d_i = \max \limits_{j=1}^{i} \left \{a_j \right \}

题解

模拟？30 分。

画图发现，如果第 i 位的值为当前数组中最大值，那么询问这个点往后的询问值一定与第 i 位的询问值相符。那么最后一位的询问值一定与第 i 位的询问值一样。现在就是要找到这个 i 位，记录下来。

考虑二分。

在这个数组中二分查询这个 i 位，首先询问一次 n 位，如果第 j 位和第 n 位相同，那么查找 j 往前的位置，不然查找 j 往后的位置，最终查找到开头的位置，那么这位置一定是 n。标记后将 a_i 清零，那么这个序列中的最大值就是 n-1，重复操作，直到确定 1 的位置。

过程在图片里面。

清零之后求 n-1 , n-2 , n-3 , ... , 1 以此类推。好了，这道题就解决了。

代码

#include <bits/stdc++.h>
using namespace std;
int ans[50005];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=n;i>=1;i--){
            printf("? 1 %d\n\n",n);
            fflush(stdout);//刷新缓存
            int biao;
            scanf("%d",&biao);
            int l=1,r=n;
            while(l<r){
                int mid=(l+r)>>1;
                int tmp;
                printf("? 1 %d\n\n",mid);
                fflush(stdout);//刷新缓存
                scanf("%d",&tmp);
                if(tmp==biao) r=mid;
                else l=mid+1;
            }
            printf("? 2 %d\n\n",r);
            fflush(stdout);//刷新缓存
            ans[r]=i;
        }
        printf("!");
        for(int i=1;i<=n;i++) printf(" %d",ans[i]);
        puts("\n");
        fflush(stdout);//刷新缓存
    }
    return 0;
}