题解：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 同步至本站。