题解：P11231 [CSP-S 2024] 决斗（民间数据）

26 Oct, 2024 10:02 PM +08:00

因为攻击顺序可以随意指定，那么 $r$ 的顺序就无所谓了。

一看数据范围 ${10}^5$ ，不妨给 $r$ 排个序，发现 $r_i$ 能打败 $r_j$ 仅当 $j<i$ 。

那么维护一个队列，把排序的 $r$ 依次放进去，每次让 $r_i$ 攻击队首。

最后看看队里剩下几个数就是答案。

#include <bits/stdc++.h>
#define i64 long long

const i64 MAXN = 1e5 + 64;

std::queue<i64> q;

i64 a[MAXN], n;

void solve()
{
    assert(scanf("%lld", &n));
    for (i64 i = 1; i <= n; ++i) assert(scanf("%lld", &a[i]));
    std::sort(a + 1, a + 1 + n, std::less<i64>());
    for (i64 i = 1; i <= n; ++i)
    {
        if (!q.empty() && q.front() < a[i]) q.pop();
        q.push(a[i]);
    }
    printf("%lld\n", (i64)q.size());
}

signed main()
{
    solve();
    return 0;
}

很难想到这其实就是 $r$ 的众数在 $r$ 中出现的次数，所以有 $O(n)$ 做法。

本文最初发表于 Luogu，于 2026-04-19 同步至本站。

题面： https://www.luogu.com.cn/problem/P11231