CSP-S 2024 T1 题解

· · 题解

解法很简单，直接求众数即可。

很显然，每个怪兽尽量发挥自己活着的价值，即尽量干掉一个比他攻击值小的怪兽。

很显然，攻击值越大应该越晚被干掉。

我们按攻击力从大到小分层。

那么如果都不相等，那应该只会留下攻防最大的那个。

设第 i 层人数为 a_i.

每一层都应该会留下 \max\{a_{i-1}-a_i,0\} 个怪兽。其实把这个值加起来就对了，但是还要解释一下为什么众数是对的。

我们发现是 a_{i-1}>a_i 这个值就是其差，否则为 0.

我们直接令 b_i=a_i-a_{i-1}，那么就是求 b 数组大于零值的和，设 b 数组选出来大于零的的值为 c 集合（即 b_{c_i}>0，且 c 是极大的），那么 a_{c_i} 是严格单调上升的。

所以说答案为 \sum b_{c_i}-b_{c_{i-1}}，即 a_{c_{|c|}}，又因 a_{c_i} 单调上升，所以 a_{c_{|c|}} 一定是 \max\{a_{c_i}\}，而 c 是极大的，所以即为 \max{a_i}.

代码如下：

#include<bits/stdc++.h>
const int N=1e5+6;
int n,x,mp[N],ans;
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&x);
        ans=std::max(ans,++mp[x]);
    }
    printf("%d\n",ans);
    return 0;
}