P13500 题解

· · 题解

题目比较典型，一眼二分。

Part 1 思路

我们考虑答案是否具有单调性，对于 x 秒，假如符合要求，那么 x - 1 秒也会符合要求（否则根本支撑不到第 x 秒），所以答案具有单调性。

那么，我们二分了 s 之后怎么判断呢？

考虑贪心策略，我们要是想让尽可能多的冰不融化，那么我们可定不会浪费每一次给冰加上 1 个单位质量的机会。

知道了这些以后，我们会发现，每次肯定是会要给前 k 小的冰加上 1 个单位，这样我们可以使用优先队列来维护。

具体的，每次把所有的数放进优先队列里，拿出前 k 小的，加上 1 以后再放进队列里即可。

但是我们会发现这样的复杂度太高，怎么优化呢？

我们整体地考虑，假如说 a_i \le s，那么在前 s 秒内这块冰就会融化，那么我们就需要至少加上 s + 1 - a_i 质量才能使它不融化。

我们在前 s 秒内最多可以给所有的冰加上 s \times k 个单位的冰，所以只需要判断 s \times k 与所有需要加上的质量的和即可。

Part 2 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int M = 1e6 + 10;
ll n, k, a[M], minn, ans;

bool check(ll s) {
    ll cnt = 0;
    for (int i = 1; i <= n; i ++) 
        if (a[i] <= s) 
            cnt += s + 1 - a[i];
    return cnt <= s * k; 
}

int main() {

    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i], minn = min(a[i], minn);
    ll l = minn - 1, r = 1e11;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else 
            r = mid - 1;
    } 
    cout << ans << "\n";

    return 0;
}

Part 3 注意事项

需要注意二分上限 r 需要赋一个比较大的数，同时也要开 long long。