P11490 Staring Contest 题解
被题目编号吸引进来的一位。
首先我们可以考虑 个整数：假设其为 。这三个整数因为在题目中是两两不同的，所以根据它们的相对大小关系，赋值为 ，共有 种情况，如下图：
可以发现，我们可以通过查询这 个数的两两之间的 值，就可以找到那个最小值的位置和最小值的值。
算法 1： 做法
所以可以根据这个来从左到右每 个数暴力枚举，找到最小值就把它给踢掉，然后再新插入一个数作为 继续暴力。每次暴力询问 次，一共就是约 次，明显过大，通过不了此题。
算法 2： 做法
我们发现询问完了把一个数踢掉了之后，剩下的那两个数就会平移到前面作为 ，而这两个数的 值是之前问过的，就可以将其代入而无需询问。这样就可以做到新插进来一个数而只需询问 次的更优的算法。但是通过不了 的点，算法仍需优化。
以下定义前缀次大值个数为 。
算法 3： 做法
我们再看上面的那个表，其实问 次都多余了。把表的最后一项 项删除，会发现并没有什么影响。因为关系就那么几种，所以只需要问两次，即 和 的值即可得到最小值的位置和数值。所以当新的一个数插进来时，只需问 次就可以求得最小值和最小值的位置。当然这对最小值在 和 时是对的，而当最小值在 时情况比较特殊。因为下一次询问还需要当前 的前提。
分析这种情况：根据之前提到的，每次操作都是把最小值剔除然后向前平移到 ，我们可以得到新 和 一定是新 加进来之前的前缀最大值和前缀次大值。当然顺序还不知道。于是当 作为最小值的时候，要么就是前缀最大值更新了，要么就是前缀次大值更新了。我们发现前缀次大值更新是完全包含前缀最大值更新这种情况的。因为当前缀最大值更新时，旧的前缀最大值就会作为新的前缀次大值。所以就可以将其当作前缀次大值更新。综上，当 作为最小值时，一定是前缀次大值更新了，由于在这种情况中询问次数要加上 ，所以就相当于总询问次数加上了总的前缀次大值个数。
算法 4：期望询问次数
注：这里的 为调和级数，即 。
因为如果使用算法 ，某些良心（？）的出题人就会卡你 corner，直接造一个前缀次大值个数极大的 corner case，就会通过不了。那么我们只能把序列 random_shuffle 一下，竟然通过了此题！这里证明一下询问次数为什么在 random_shuffle 之后就是对的。
因为序列重新打乱过了，所以这里的复杂度就会是期望询问次数。而打乱过后的期望询问次数依然是 。之前说到前缀次大值个数可以通过两种情况更新：
新的前缀最大值更新了旧的前缀最大值，而旧的前缀最大值就成为了新的前缀次大值。
这种情况就要求期望前缀最大值的个数。我们首先可以把序列离散化一下，就变成了一个 的排列。
容易如果数 成为了前缀最大值，那么比 大的数就一定在 的后面，所以留给前面的空间至少也必须要有 。
这种情况下 对答案的贡献就是 。所以期望前缀最大值的个数就是 。
注：。
新的数比前缀最大值小，但比前缀次大值大。这种情况也可以用类似上面的证明求，这种数的期望也不会超过 。
所以这种期望询问次数 ，可以通过此题。
Code:
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
34
35
36
37
38
39
40
41
42
|
#include <bits/stdc++.h>
using namespace std;
int pos[4], val[4], ans[2009], idx[2009];
int main(){
int n;
cin>>n;
cout<<"? 1 2\n";
fflush(stdout);
cin>>val[1];
pos[1] = 1, pos[2] = 2;
for(int i=1;i<=n;i++){
idx[i] = i;
}
random_shuffle(idx+3, idx+1+n);
for(int i=3;i<=n;i++){
pos[3] = idx[i];
cout<<"? "<<pos[2]<<' '<<pos[3]<<'\n';
fflush(stdout);
cin>>val[2];
if(val[1] == val[2]){
cout<<"? "<<pos[1]<<' '<<pos[3]<<'\n';
fflush(stdout);
cin>>val[3];
ans[pos[2]] = val[1];
pos[2] = pos[3];
val[1] = val[3];
}else if(val[1] < val[2]){
ans[pos[1]] = val[1];
pos[1] = pos[2], pos[2] = pos[3];
val[1] = val[2];
}else{
ans[pos[3]] = val[2];
}
}
ans[pos[1]] = ans[pos[2]] = val[1];
cout<<"!";
for(int i=1;i<=n;i++){
cout<<' '<<ans[i];
}
return 0;
}
|
