[Codeforces Global Round 17][Codeforces 1610E. AmShZ and G.O.A.T.]
DeaphetS
·
·
题解
为自己的博客引流
既然要求的是最大的好序列，就需要考虑排除所有的不安定因素，即先思考什么样的子序列是非法的。
另外可以证明，一个非法序列 $c$ 里一定存在一个长度为 $3$ 的非法子序列，证明方式采用反证法。
令 $m=\lceil \frac{k}{2}\rceil$，考虑 $c_m$ 的大小，既然 $c$ 是一个非法序列，那么 $c_m$ 就一定要严格大于序列的平均值。然而由于 $c$ 中不存在一个长度为 $3$ 的非法子序列，据此得出对任意的 $i$，$c_i,c_m,c_{k-i+1}$ 一定是一个合法序列，那么就有 $c_i+c_{k-i+1}\ge 2c_m$（这一结论在 $i=m$ 或 $k-i+1=m$ 时也显然成立）。把 $\sum c_i$ 乘以二后首尾配对就能得到：
$$2\sum_{i=1}^k c_i=\sum_{i=1}^{k} {c_i+c_{k-i+1}}\ge2k\cdot c_m$$
把上面的这个式子两边同除 $2k$ 就能得出，$c_m\le \frac{\sum_{i=1}^k c_i}{k}$ ，与之前的 $c_m$ 要严格大于序列的平均值发生矛盾，于是得出 $c$ 里一定存在一个长度为 $3$ 的非法子序列，**证毕**。
于是一个好的序列就必须保证：序列中不存在三个数 $a\le b\le c$，使得 $2b>a+c$。必要性显然，充分性在刚刚得到了证明。
那么我们在构造一个尽可能大的子序列时，就需要时刻保证对任意的 $a\le b\le c$，有 $b\le \frac{a+c}{2}$。我们来考虑一下往答案序列里面一直加数的过程，假设一开始序列里有两个数 $x,y$，不妨设 $x,y$ 就分别是最终答案中的最小值和最大值，那么下一个被加进来的数就必须满足 $x\le z\le \frac{x+y}{2}$。不难通过想象（或在数轴上画图）得出，这一操作相当于让前两个数之间的间隔减半。于是这个加数的操作不会超过 $O(\log n)$ 次，当然除了最后可能会把所有与 $x$ 相同的数字全部加进去。
回顾这个构造序列的过程，本着贪心的原则可以得出，当确定了序列中的最小值 $a$ 之后，一定是先把所有数字中的最大值加进去来提高初始两个数之间的间隔。接下来就是不断加入最大的满足 $x\le z\le \frac{x+y}{2}$ 的数字 $z$，这样就能构造出一个以 $a$ 为最小值的最大序列。这里要注意，由于在序列中，只有最小值是可以重复出现的（若不然，则会有 $\{x,y,y\},x<y$ 使得序列变坏），所以序列的最小值是需要枚举的。那么我们枚举序列中的最小值，然后再模拟生成序列的过程，每次二分找到最大的满足条件的数，就能得到最终的答案，时间复杂度为 $O(n\log n\log W)$。
当然作为一篇严谨的题解，我们还需要补充说明一下，按照此法生成的序列一定是一个好序列。实际上只要说明任意一个大小为 $3$ 的子序列都是合法序列就好了，以下为证明过程：
对这个生成的序列 $b$，可以根据生成序列的过程得出，$b_{i}\le \frac{b_{i+1}+b_1}{2}$，从而有 $b_{i+1}-b_1\ge 2(b_i-b_1)$。那么对任意的 $j>i$，也能得出 $b_j-b_1\ge 2(b_i-b_1)$，移项得到 $b_j-b_i\ge b_i-b_1$。
于是对任意的 $i<j<k$，必然有 $b_k-b_j\ge b_j-b_1\ge b_j-b_i$，从而推出 $2b_j\le b_i+b_k$，得到 $b_i,b_j,b_k$ 是一个合法序列，**证毕**。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 200010
int T,n,a[N];
int main()
{
scanf("%d",&T);
while(T--){
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1,nxt=1;i<=n;i=nxt){
while(nxt<=n && a[nxt]==a[i])nxt++;
if(nxt>n){
ans=max(ans,nxt-i);
break;
}
int j=n,cnt=1;
while(nxt<=j){
j=upper_bound(a+nxt,a+j,(a[i]+a[j])/2)-a-1;
if(j<nxt)break;
cnt++;
}
ans=max(ans,cnt+nxt-i);
}
printf("%d\n",n-ans);
}
}
```