题目链接:https://codeforces.com/contest/1163/problem/B2
题意是删除一个数后,求一个最大的距离x,使得1-x中的数的出现个数相同
遍历每一位,对第i位维护一个1-i的所有数的出现次数,以及所有数的出现次数的出现次数,然后讨论一下情况就好了,比较绕。
AC代码:
#include <bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
ll pre[maxn];
int n;
int main()
{
scanf("%d", &n);
map<ll,ll> a, b;
for(int i=0;i<n;i++){
scanf("%lld", &pre[i]);
}
ll ans = 0;
ll pos = 0;
for(int i=0;i<n;i++){
a[pre[i]] ++;
b[a[pre[i]]] ++;
if(a[pre[i]] != 1) b[a[pre[i]] - 1] --;
if(pos < a[pre[i]]) pos = a[pre[i]];
if(i + 1 == b[1]) ans = i + 1;
if(b[1] == 1 && i + 1 == 1 + b[pos] * pos) ans = i + 1;
if(b[pos] == 1 && i + 1 == b[pos - 1] * (pos - 1) + pos) ans = i + 1;
}
printf("%lld\n", ans);
return 0;
}