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 代码

CPP

#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。

文章操作

Part 1 思路

Part 2 代码

Part 3 注意事项

相关推荐

评论

P13500 题解