好题

题目链接 Cat Party

题目大致意思 题目会给出n天，每天都会有一个颜色$u_i$，找出最大的x使删除前x天中的某一天，使得剩下的x-1天出现过的颜色个数相同

如果x满足以下四个条件之一，那么这个x就是合法的。

• 前x天内只出现过一种颜色
• 前x天内出现过x种颜色，每种颜色的个数为1
• 前x天内只有一种颜色出现过一次，既个数为1，其他若干种颜色的个数相同。
• 前x天内出现个数最多的颜色只有一种，其他种类的颜色个数相同，且这个最多个数的颜色比这些颜色个数多1

可以发现，我们每次判断x是否合法几乎只与颜色个数为1的和颜色个数最多的那些颜色有关。所以我们就可用数组来保存这些颜色的信息，然后O(1)判断，总复杂度为O(n).
具体看代码实现.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<set>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, x,ans, mx, cnt[N], f[N];
//f[i] 颜色为i的个数
//cnt[i]表示个数为i的颜色的种类
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &x);
		cnt[f[x]]--;//x要加1，所以原来种类的要减去1
		f[x]++;
		cnt[f[x]]++;
		mx = max(mx, f[x]);//保存出现最多的颜色的个数
		//每种颜色的个数都是1
		if (cnt[1] == i) ans = i;
		//只有一种颜色，i个
		else if (cnt[i] == 1) ans = i;
		//只有一种颜色个数是一，其他若干种颜色个数相同
		else if (cnt[1] == 1 && cnt[mx] * mx == i - 1) ans = i;
		//个数最多的颜色的个数为mx,它的种类必须为1，并且比其他种类的颜色多1个，且其他种类的颜色的个数必须相同
		else if (cnt[mx - 1] * (mx - 1) == i - mx&&cnt[mx] == 1) ans = i;
	}
	printf("%d\n", ans);
	return 0;
}