ICPC 2019 Hong Kong E（思维）

[题目链接](https://vjudge.net/problem/Gym-102452E) ------------ 观察数据范围想到枚举每一个数$O(n)$判断 对于一个数$x$，比$x$大的数用$1$表示，比$x$小的数用$0$表示 然后仔细观察发现，如果经过若干次操作后$1$与$0$的数量相同，那么$x$一定可以被留下来 要使 $0,1$ 的数量变得相等，只有 $111$ 或者 $000$ 这样的情况有贡献 比如$x$小于$(n+1)/2$，需要删除一些比$x$大的数字 形如$110,101,011...$的连续三个数，并不会影响最后$1$的数量与$0$的数量的大小关系 只有$111$才能使$1$的数量可能与$0$的数量相同 ，且需要删除的次数为$(n+1)/2-x$ $O(n)$遍历求出最多能删除的次数，判断大小 ------------ ```cpp #include <bits/stdc++.h> using namespace std; const int M=5e3+5; int n,a[M]; int check(int pos) { int cnt=abs(a[pos]-(n+1)/2); int now=0,num=0,k=(a[pos]<(n+1)/2); for(int i=1;i<=n;i++) { if(i==pos){now=0;continue;} int t=(a[i]>a[pos]); if(t!=k)now=max(now-1,0); else { now++; if(now==3)num++,now-=2; } } return num>=cnt; } int main() { int T;scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)if(check(i))printf("1");else printf("0"); puts(""); } return 0; } ```