【题目讲解】序列变换

 序列变换

描述

你有一个长度为 n 的整数序列 a 。你想要把序列 a 的所有数字变成相同的。你可以选定一个序列出现的数字 x ，每次选一个不包含数字 x 的区间 [l,r] 删除所有数字。求最少操作次数。

输入描述

第一行包含一个整数 t ( 1≤t≤2⋅104 ) 表示测试数据的组数；

每组数据第一行包含一个整数 n ( 1≤n≤2⋅105 ) ，表示数组长度 ，第二行包含 n 个整数 a1​,a2​,…,an​ ( 1≤ai​≤n )。保证 n 的总和不超过 2⋅105 ( ∑n≤2⋅105 )。

输出描述

对每个测试数据，输出一个数表示最少操作次数。

难度：提高-

#include
using namespace std;
int a[600000],f[600000];
int main()
{
	int t,n,ans=0;
	cin>>t;
	for(int i=0;i
	{
		ans=1e9;
		cin>>n;
		for(int j=1;j<=n;j++)f[j]=0;
		for(int j=1;j<=n;j++)
		{
			cin>>a[j];
			if(a[j]!=a[j-1]) f[a[j]]++;
		}
		int st=f[a[1]],ed=f[a[n]];
		f[a[1]]=0;
		f[a[n]]=0;
		for(int j=2;j<=n-1;j++)
		{
			if(f[a[j]]>0)ans=min(ans,f[a[j]]+1);
		}
		if(a[1]!=a[n])ans=min(ans,min(st,ed));
		else ans=min(ans,st-1);
		cout<
	}
}