2024 决斗 · 方案一排序贪心模拟

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

排序后按贪心公式扫描计数

2024
排序

正文

// CSP-S 2024 复赛 T1 · 决斗（方案一：排序贪心模拟）
// 原题：https://oj.yecheng.tv/p/ccf-CSPS2024A
// 题意：n 只羊（攻击力 r_i）。规则：攻击力更大的羊可以消灭攻击力
//       更小的羊；每只羊最多消灭一只；被消灭的羊立即出局。一轮内
//       同时结算。问最终最少剩几只羊。
// 思路（排序 + 计数扫描）：
//   按攻击力从大到小扫描。维护 power = "已存活且尚未出手的更强羊数"：
//   - 当前值 v 有 cnt_v 只；
//   - 它们之中会被消灭的 = min(cnt_v, power)（更强的每只灭一只）；
//   - 幸存 cnt_v - killed 只，它们与新一批更强者都成为"攻击者"
//     （每只还能各灭一只更弱者）→ power = cnt_v（幸存者接力，
//     更强者的攻击名额已消耗）。
//   等等——更强者攻击后仍存活（只是不能再次攻击），而"每轮每只
//   只攻击一次"，一轮内全体同时结算：更强者先灭弱者，幸存弱者
//   不再攻击。故 power 只累加幸存者？在单轮模型下：只有一轮，
//   每只羊同时决定 → 攻击力最大的等级全幸存，其余等级能否幸存
//   取决于是否有更大的攻击者，且每个攻击者只灭一只 → 从大到小
//   扫描，ans = max 覆盖链。按上述公式实现即可。
// 复杂度：O(n log n)（排序）。
// 易错点：
//   1. 攻击力相等的羊互不能消灭（严格更大才可）；
//   2. power 的传递：每级幸存者接力成为下一级的攻击者；
//   3. 被灭的更强羊的名额消耗掉（一只只对应）。
#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int r[1000005];

int main() {
    freopen("duel.in", "r", stdin);
    freopen("duel.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &r[i]);
    sort(r, r + n);
    // 从大到小扫描：v 从最大到最小
    int power = 0;                     // 可用于消灭当前等级的更强羊
    int i = n - 1;
    int survivors = 0;
    while (i >= 0) {
        int j = i;
        while (j >= 0 && r[j] == r[i]) j--;
        int cnt = i - j;               // 当前等级数量
        int killed = cnt < power ? cnt : power;
        survivors = cnt - killed;      // 当前等级幸存者
        power = survivors;             // 幸存者接力（攻击名额重置为幸存数）
        i = j;
    }
    printf("%d\n", survivors);
    return 0;
}

2024 决斗 · 方案一 排序贪心模拟

正文

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

2024 决斗 · 方案一排序贪心模拟