CF1163B1 Cat Party (Easy Edition)题解

_little_Cabbage_ · 2023-11-19 11:28:52 · 题解

CF1163B1 Cat Party (Easy Edition)题解

博客观看食用更佳

这题其实非常水。

根据题意，我们可以知道在子序列 [1,x] 中，要满足其中任一元素后每个数出现的次数相同这个条件，有如下三种情况：

• 所有元素出现次数都为 1，如序列 [1,2,3,4,5]
• 除了一个出现次数为 1 的元素，其他元素的出现次数都相等，如序列 [1,2,2,3,3,4,4,5,5]
• 除了一个出现次数比其他数的出现次数多 1 的元素，其他元素的出现次数都相等，如序列 [1,1,2,2,3,3,4,4,4,5,5]

为什么呢？

让我们来分析一下：

• 对于第一种情况，以序列 [1,2,3,4,5] 为例，删除其中任何一个数以后都能满足其中任一元素后每个数出现的次数相同
• 对于第二种情况，以序列 [1,2,2,3,3,4,4,5,5] 为例，删除 1 以后就能满足其中任一元素后每个数出现的次数相同
• 对于第三种情况，以序列 [1,1,2,2,3,3,4,4,4,5,5] 为例，删除任意一个 4 以后就能满足其中任一元素后每个数出现的次数相同

这样就很容易写出AC代码了。

AC代码：

#include<bits/stdc++.h>
#define caozuo ret[cnt[u[i]]]--;cnt[u[i]]++;ret[cnt[u[i]]]++;
using namespace std;
int cnt[100010],ret[100010],u[100010];
int main()
{
    int n;
    scanf("%d",&n);
    int ans=0;
    int mx=INT_MIN;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&u[i]);
        caozuo
        mx=max(mx,cnt[u[i]]);
        if(mx==1)
        {
            ans=i;
            continue;
        }
        if(ret[mx]*mx==i-1)
        {
            ans=i;
            continue;
        }
        if((ret[(mx-1)]+1)*(mx-1)==i-1)
        {
            ans=i;
            continue;
        }
    }
    printf("%d",ans);
}

AC记录