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

wangbinfeng · 2020-11-15 11:33:26 · 题解

考点：

• [ ] 【4】二分法；
• [ ] 【5】快速排序或【3】算法模板库中的函数：min、max、swap、sort。

思路：

考虑到一个怪兽能打破一个 r_i 小于它的怪兽，要使剩下的怪兽最多当且仅当最多的怪兽可以打破其他怪兽。

那么希望一个怪兽打破的怪兽是最近的小于它的怪兽（设这两个怪兽分别为 i,j，则不存在 r_i<r_k<r_j），那么可以使用二分来来寻找到这一需求。

考虑逆向实现。具体地，先对输入的 r 进行排序，然后枚举所有的 r，对于枚举到的 r_i，用二分找到比他大的最近的怪兽 j，并标记这个怪兽已被使用掉打破其他怪兽的次数。

本人使用了 lower_bound 代替手写二分，发现到寻找 k 时如果存在 k 就会返回第一个 k 的位置，否则返回第一个大于 k 的位置。那么用 lower_bound 寻找 r_i+1 即可。而对于一个怪兽被用掉了打破其他怪兽的次数，我们可以姑且在其被更多次寻找时 r_i-1，而主动寻找时再加回去即可。

时间复杂度 \Theta(n \log_2 n)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int n, a[maxn], anss;
bitset<maxn> vis, ans;
signed main()
{
//  freopen("dat.in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1, k = 1; i <= n; i++)
    {
        k = lower_bound(a + k, a + n + 1, a[i] + 1 + vis[i]) - a; // 发现二分寻找的怪兽单调递增，那么二分的左端点可以直接赋值为上次的 k。
        while (vis[k])
            k++;
        if (k > n)
            continue;
        vis[k] = true, a[k]--, ans[i] = true;
    }
    for (int i = 1; i <= n; i++)
        anss += !ans[i];
    cout << anss << endl;
//  for (int i = 1; i <= n; i++)
//      cerr << vis[i] << ' ';
//  cerr << endl;
//  for (int i = 1; i <= n; i++)
//      cerr << ans[i] << ' ';
}