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

XoCeLHsL · 2024-10-26 22:02:49 · 题解

因为攻击顺序可以随意指定，那么 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) 做法。