Codeforces Round #558 B2. Cat Party (Hard Edition)

川长思鸟来 2021-12-04 04:23 81阅读 0赞

# 题面： #

[传送门 ][Link 1]

# 题目描述： #

题意：确定最大的x，使去除掉前x天的其中一天后，所有不同数字的数量相等。

# 题目分析： #

可能是我太久没打cf了，水题都做不出来?。

这道题的关键在于：要记录相同数量，的不同数字，有多少个。为什么要这样记录呢？我们分析一下符合题意的有多少种情况：

> 1.每个不同的数字只出现1次，例：1，2，3，4，5
> 
> 2.只有一种数字，例：1，1，1，1，1
> 
> 3.只有一种数字出现1次，其他数字出现的次数相同，例：1，1，1，2，2，2，3
> 
> 4.有一种数字出现的次数比其他数字都多出1次，例：1，1，2，2，3，3，3

从这些情况可以看出：用“普通”的方法（直接遍历循环检查次数）是行不通的（会超时，这个是O(n^2)的做法）。所以问题就在于如何优化检查“次数”。这时我们只要：多开一个记录 “相同数量有多少个不同数字” 的数组，举个例子：

> 我们开一个叫same\_cnt的数组，那么对于这组数据：1，1，2，2，3，3，4，4，4
> 
> 其中same\_cnt\[2\] = 3（因为数字1，2，3的数量是2，共3个）
> 
> same\_cnt\[3\] = 1（因为数字4的数量是3，共1个）

接下来，我们从小到大枚举x的值就行了，判断可以用这个辅助数组O(1)判断出来。

AC代码：

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const int maxn = 1e5+5;
     4 int u[maxn];
     5 int cnt[maxn];
     6 int same_cnt[maxn];
     7 
     8 int main(){
     9     int n;
    10     scanf("%d", &n);
    11     for(int i = 1; i <= n; i++){
    12         scanf("%d", &u[i]);
    13     }
    14     
    15     int res = 0;
    16     int mx = 0;
    17     for(int i = 1; i <= n; i++){
    18         cnt[u[i]]++;
    19         same_cnt[cnt[u[i]]-1]--;
    20         same_cnt[cnt[u[i]]]++;
    21         
    22         mx = max(mx, cnt[u[i]]);   //小技巧，自己领会一下
    23         int ok = 0;
    24         
    25         if(same_cnt[1] == i) ok = 1;     //第一种情况：数量为1的有i个                           
    26         else if(same_cnt[i] == 1) ok = 1;   //第二种情况：数量为i的有1个
    27         //第三种情况
    28         else if(same_cnt[1] == 1 && same_cnt[mx]*mx == i-1) ok = 1;
    29         //第四种情况
    30         else if(same_cnt[mx] == 1 && same_cnt[mx-1]*(mx-1) == i-mx) ok = 1;
    31         
    32         if(ok) res = i;
    33     }
    34     
    35     printf("%d\n", res);
    36     return 0;
    37 }

转载于:https://www.cnblogs.com/happy-MEdge/p/11175744.html

[Link 1]: http://codeforces.com/contest/1163/problem/B2