思维题
这次比赛打的太烂了。。
一开始还去离散化了一下。。发现完全不需要。
要求找到一个前缀，删除一个数后其他数出现次数相等。
我们肯定要统计每一个数出现的次数，然后考虑符合题意的情况。
显然有四种：
-
每个数都出现一次
-
整个前缀只有一种数
-
有一个数出现的次数和其他数不同，如果这个数出现的次数小于其他数出现的次数，这个数出现的次数一定是1
-
同上，但是大于其他数出现的次数，只能多1次
符合上面任意一种，就找到了一个前缀啦。
为了方便统计，我们用col[i]数组表示每个数i出现的次数，用freq[j]反查找出现次数为j的数的种类
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int X = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
const int N = 100005;
int a[N], col[N], freq[N];
int main(){
int n = read(), mx = 0, ans = 1;
for(int i = 1; i <= n; i ++) a[i] = read();
for(int i = 1; i <= n; i ++){
freq[col[a[i]]] --, col[a[i]] ++, freq[col[a[i]]] ++;
mx = max(mx, col[a[i]]);
bool good = false;
if(freq[1] == i) good = true;
else if(freq[i] == 1) good = true;
else if(freq[1] == 1 && freq[mx] * mx == i - 1) good = true;
else if(freq[mx] == 1 && freq[mx - 1] * (mx - 1) == i - mx) good = true;
if(good) ans = i;
}
cout << ans << endl;
return 0;
}