题目描述

输入描述

输出描述

示例一

//输入
6
3
1 2 1
5
1 2 2 1 2
11
2 2 1 2 2 1 1 2 2 1 2
1
1
5
1 2 3 4 5
10
4 1 5 5 2 2 5 2 4 2

//输出
2
2
6
1
1
2

思路

抓住题目中col的特点，col有n种颜色，每次删除时，我们从后往前找，找的是整个剩余的数字串中，最晚出现的那个数字，然后删除该数字及该数字后面的所有数字。然后剩余数字串中的数字的种类由cnt进行记录。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n;
int a[200010],vis[200010];
map<int,int>m;

void calc()
{
    scanf("%d",&n);
    int cnt =0,cnt1=0,cnt2=0,ans=0;
    for(int i =1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(!vis[a[i]])cnt++;
        vis[a[i]]++;//记录每个数字出现的次数
    }
    for(int i =n;i>=1;i--)
    {
        m[a[i]]++;vis[a[i]]--;
        if(m[a[i]]==1)cnt1++;
        if(vis[a[i]]==0)cnt2++;//当vis[a[i]]==0时表示该位置是该数字最后一次出现的位置，下一次删除时，没有该数字了，用cnt2记录
        if(cnt1==cnt)
        {
            ans++;
            cnt-=cnt2;
            m.clear();
            cnt1=0;
            cnt2=0;
        }
    }
    printf("%d\n",ans);
    
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        calc();
    }
    return 0;
}