P11231 [CSP-S 2024] 决斗

sLMxf · 2024-10-26 21:35:44 · 题解

简述题意

每个怪兽有一个实力 r_i，每个怪兽只可以欺负实力严格小于自己的怪兽，被成功欺负的怪兽出局。当未退出游戏的怪兽都已发起过攻击时，游戏结束。规定一种方案使得未退出游戏的怪兽数量尽可能少。

算法分析

显然，对于 a<r_i,b<r_i，a,b 在 r_i 面前是等价的（都能被欺负）。

定义 sum_k 表示 r_i=k 的怪兽个数，cnt 为对于实力为 [1,i-1] 的怪兽的最优解。

所以按实力从小到大欺负，有两种情况：

• 如当前 sum_k\le cnt，欺负 sum _k 只即可。即 cnt\gets cnt。
• 否则，欺负当前所有怪兽，即 cnt\gets sum_k。

上面的过程可看做 cnt=\max sum_k。

然后这题就做完了。

诶等等，如果这个数据：

3
1 2 2

有一只怪兽好像没有欺负别人啊？

其实让剩下相同的再互相欺负一遍即可。

时间复杂度 O(n+A)，A 为 r_i 的值域。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
signed main()
{
    int n,x,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a[x]++;
    }
    for(int i=1;i<=100000;i++) ans=max(ans,a[i]);
    cout<<ans;
    return 0;
}