2024 决斗 · 方案二桶计数线性扫描

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 998 字

桶计数代替排序，同款贪心公式线性扫

2024
排序

正文

// CSP-S 2024 复赛 T1 · 决斗（方案二：桶计数线性扫描）
// 原题：https://oj.yecheng.tv/p/ccf-CSPS2024A
// 题意：同方案一（r_i ≤ 1e5，可用桶省去排序）。
// 思路（桶 + 同样的贪心公式）：
//   cnt[v] = 攻击力为 v 的羊数。从 v = maxR 到 1 扫描，
//   复用方案一的接力公式：killed = min(cnt[v], power)，
//   survivors = cnt[v] - killed，power = survivors。
//   复杂度 O(n + V)（V = 值域 1e5），常数比排序小。
// 复杂度：O(n + V)。
// 易错点：
//   1. 扫描方向从大到小，别写反；
//   2. power 初始 0（最大等级之上没有攻击者）；
//   3. 答案 = 扫完后的 survivors（最小等级的幸存数）。
#include <cstdio>

int n;
int cnt[1000005];

int main() {
    freopen("duel.in", "r", stdin);
    freopen("duel.out", "w", stdout);
    scanf("%d", &n);
    int mx = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        cnt[x]++;
        if (x > mx) mx = x;
    }
    int power = 0, survivors = 0;
    for (int v = mx; v >= 1; v--) {
        if (!cnt[v]) continue;
        int killed = cnt[v] < power ? cnt[v] : power;
        survivors = cnt[v] - killed;
        power = survivors;
    }
    printf("%d\n", survivors);
    return 0;
}

2024 决斗 · 方案二 桶计数线性扫描

正文

CSP-S 标程 · 复赛真题的其它内容

2024 决斗 · 方案二桶计数线性扫描