E-ACM中的CM题

现在在你前面有 nnn 个地雷

刚刚学会瞬移的你决定排走所有地雷

遗憾的是，你的初始排雷能力 m=0m = 0m=0，但你知道

当排雷能力为 mmm 时，你可以任何时刻在当前位置 lll 处将[l,l+m][l, l+m][l,l+m] 中的雷全部排走

也可以在任何时刻任何地点，将排雷能力从 mmm 变为 m+1m+1m+1

以上两种操作都需要花费 1 的时间，但瞬移不花费时间！

求排所有雷所需最小时间！

思路

枚举m长度二分求次数即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N];
int n, ans;
void check(int len) {
    int res = len - 1;
    for (int i = 1; i <= n; i++) {
        int l = i, r = n;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (a[mid] - a[i] + 1 > len)
                r = mid - 1;
            else
                l = mid;
        }
        res++;
        i = l;
        if (l == n)
            break;
    }
    ans = min(ans, res);
}

void solve() {
    int num;
    cin >> num;
    n = 0;
    map<int, int> mp;
    for (int i = 1; i <= num; i++) {
        int x;
        cin >> x;
        if (!mp[x]) {
            a[++n] = x;
        }
        mp[x] = 1;
    }
    ans = n;
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        check(i);
    }
    cout << ans << endl;
}
signed main() {
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}