CF1163B1 题解

ikunTLE · 2024-12-16 22:13:57 · 题解

题目传送门

思路

我们发现题面中的 u_i\le10，数据十分小，可以利用这一点解题。我们用 C_x 表示 x 总共出现的次数，再用 S_y 表示 y 在 C_x 中的次数。

然后，用循环变量 i，遍历 u，先将 S 与 C 按照新的 u_i 更新。然后判断 S 中的第 1 个点，第 i 个点，以及 C_{u_i} 中的最大值 M 以及 M-1 的点是否满足题目条件即可。

过程

读入 n，u_i。

循环变量 i 遍历 1 到 n：

更新 S 与 C，即：S_{C_{u_i}}\gets S_{C_{u_i}}-1，C_{u_i}\gets C_{u_i}+1，S_{C_{u_i}}\gets S_{C_{u_i}}-1。

然后更新最大值 M：M=\max(M,C_{u_i})。

判断，如果满足以下任意一条，则将答案更新为 i：

输出答案。

注意事项

• 注意特判 i=1 的情况。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e5+10;
int a[N],sum[N],cnt[20];
int main(){
    int n=read();
    if(n==1)
        return printf("1\n"),0;
    for(int i=1;i<=n;++i)
        a[i]=read();
    --sum[cnt[a[1]]],++cnt[a[1]],++sum[cnt[a[1]]];
    int maxx=cnt[a[1]],ans=0;
    for(int i=2;i<=n;++i){
        --sum[cnt[a[i]]],++cnt[a[i]],++sum[cnt[a[i]]];
        maxx=max(maxx,cnt[a[i]]);
        if(sum[i]==1||sum[1]==i||sum[1]==1&&sum[maxx]*maxx==i-1||sum[maxx]==1&&sum[maxx-1]*(maxx-1)+maxx==i)
            ans=i;
    }
    printf("%d\n",ans);
    return 0;
}