ZZULIOJ 2739 无

给一个序列a，包含n个整数，a的序号由1到n。你可以选择一个整数x（只能选一次，且x在序列a中），你可以进行一次或者多次下列操作：
你可以选择第r个到第l个连续的数字（1<=r<=l<=n），变成x，但有一个前提，第r到第l个数字中不能有等于x的数字。
求最少多少次操作，可以使整个序列a中的数都变成你所选的x。
例如n=6，a={1,3,2,4,1,2},你可以选择x=1，进行第一次操作，r=2，l=4，所以此时a={1,1,1,1,1,2}。再次进行操作，r=6，l=6，此时序列a={1,1,1,1,1,1}。

输入第1行为一个整数t(1≤n≤10)，代表测试的组数。
下面有t组测试数据每组有两行
第一行包括一个整数n，表示序列a有n个整数（1<=n<=200000）
第二行包括n个整数，a1，a2，a3，…，an （1<=ai<=n）

输出最小的操作次数，使序列a中的整数全变为x

5
3
1 1 1
5
1 2 3 4 5
5
1 2 3 2 1
7
1 2 3 1 2 3 1
11
2 2 1 2 3 2 1 2 3 1 2

0
1
1
2
3

本题思路很好想，就是找相同的数，看它们之间有几个间隔是大于1的，找出最小的间隔数就好了，但难点就在怎么实现了；

#include
#include
struct message {
	int zhi;
	bool panduan;  //用来判断该数是否被比较过
};
int main()
{
	int a,b,c,d,e,f,i,min;
	scanf("%d",&a);
	while(a--)
	{
		scanf("%d",&b);
		struct message x[b];
		for(c=0;c 
这段代码对于思路的实现是没有问题的，但是时间效率太低，最坏的情况比如一个200000长度的数组要从当前位置遍历200000下，时间直接超限，这里我们使用空间换时间优化；
 
正确代码 
#include
#include
int x[200005];    //记录是否出现过此数（看对于下标是否为0）
int y[200005];    //记录此数上一次出现位置（记录于对应下标）
int z[200005];    //记录大于1的间隔数
int main()
{
    int a,b,c,d,e,f,i,min;
    scanf("%d",&a);
    while(a--)
    {
        min=200000;
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        memset(z,0,sizeof(z));
        scanf("%d",&b);
        for(c=1;c<=b;c++)
        {
            scanf("%d",&d);
            if(x[d]==0)
            {
                x[d]++;
            }
            if(c-y[d]>1) //看间隔是否大于1
            z[d]++;
            y[d]=c;     //更新上一次出现的地方
        }
        for(c=1;c<=b;c++)     //这里对最后一个数讨论一下，除了最后一个数，其他出现过的数对应的间隔数都要加1
        {
            if(x[c]!=0&&c!=d)
            {
            z[c]++;
           }
        }
        for(c=1;c<=b;c++)
        {
            if(x[c]!=0&&z[c]