P11231 [CSP-S 2024] 决斗 题解

· · 个人记录

题外话

开考五分钟想到正解，又过五分钟AC T1（建议降红）

Solution

看到没有头绪的题目，手推一遍样例！！！

样例1：让两个 r = 2 的分别去打两个 r = 1 的，再让那个 r = 3 的去打其中一个 r = 2 的，剩下 r = 2 和 3的各一个，共剩 2 个

样例2：让两个 r = 2417 的去打其中两个 r = 136 的，剩下 r = 136 的 6 个 ， r = 2417 的 2 个，共剩 8 个

这里有一个结论：数列 r 中众数的出现次数就是答案

证明如下：

显然， a > b > c 时，b 杀 c 然后 a 杀 b 一定是最优的

所以，把所有怪兽按 r_i 分层，令x为众数，如下图

记 i 在 r 中的出现次数为mp_i , 很容易看出：从 x+1 到 最大值 ，进行最优方案案操作后，剩余的怪兽数 \le mp_x

同理，从 1 到 x-1 ，进行最优方案操作后，剩余的怪兽数也 \le mp_x ， 如下图：

此时，攻击力为 x 的怪兽可以完全消灭下层的怪兽（即蓝色部分被消灭），上层的怪兽（黑色）可以消灭部分攻击力为 x 的怪兽，最终结果如下图：

剩余数量为 mp_x , 即众数的出现次数

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxr = 1e5 + 5;
int mp[maxr];
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) 
    {
        int x;
        cin >> x;
        mp[x] ++;
    }
    int ans = -1e9;
    for(int i = 1;i <= 1e5;i++)
    {
        ans = max(ans,mp[i]);
    }
    cout << ans << endl;
    return 0;
}