rt

link

希望大佬能提供hack数据或正确性证明。

---

这是赛时瞎搞的做法。

#include<iostream>
using namespace std;
//nxt 后继，存的是下标
int t,n,cnt,f,a[105],nxt[105],vis[106];
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){cin>>a[i];vis[i]=0;}
		nxt[n]=1;
		for(int i=1;i<n;i++) nxt[i]=i+1;
		f=1;
		//cout<<head[1]<<tail[1];		
		cnt=0;
		while(f==1){
			f=0;
			for(int i=1;i<=n;i++){
				//cout<<nxt[i]<<endl;
				if(a[i]!=a[nxt[nxt[i]]]&&vis[nxt[i]]==0){
					vis[nxt[i]]=1;
					nxt[i]=nxt[nxt[i]];
					f=1;
					cnt++;
					break;
				}
			}
		}
		//cout<<cnt<<endl;
		if(cnt==n) cout<<cnt<<endl;
		else cout<<cnt+(n-cnt)/2+1<<endl;		
	}
}

大致思路是只要一个数两边的数不同，那这个数就可以删，然后模拟这个过程。

但同机房的大佬从第一个开始判会wa，而我存的只有后继，因此是从第二个开始删的，就不会wa。