「Codeforces 505E」Mr. Kitayuta vs. Bamboos
题目传送门
题意
有\(n\)根竹子，竹子\(i\)初始高度为\(h_i\)，每天晚上会长高\(a_i\)。
每天白天，你可以选择\(k\)根竹子（同一根竹子在同一个白天可以多次选择），把他们的高度减少\(p\)，若竹子当前高度\(-p\)后\(<0\)，则竹子高度变为\(0\)。
最小化\(m\)天后最高的竹子的高度。
题解
首先最小化最大的...这种问题，显然可以用二分答案。
二分\(m\)天后最高的竹子的高度\(H\)，然后问题就变成了判定性问题：是否存在一种方案，使得\(m\)天后竹子高度都\(\le H\)。
考虑怎么解决这个判定性问题。
如果按照题意一天一天模拟，就需要考虑把竹子高度减\(p\)后\(<0\)的情况，会比较麻烦。
所以我们尝试倒着模拟这一过程。
即：竹子初始高度都设为\(H\)，每根竹子每天会减少\(a_i\)的高度，然后你可以选择\(k\)根竹子，把它们“拔高”\(p\)。问\(m\)天后竹子高度是否都\(\ge h_i\)。
此时你必须保证竹子减少\(a_i\)的高度后不会\(<0\)。
这样就好做了。我们用一个堆维护 当前状态下继续减少高度而不“拔高”，第\(m\)天结束后竹子高度会\(<h_i\)的竹子 一直减少高度 多少天后的高度会\(<0\)。
（不理解这句话可以尝试看代码理解）
每次取出最快\(<0\)的竹子，对它“拔高”即可。注意中间可能会出现无论怎么“拔高”还是会\(<0\)的竹子，此时直接返回错误即可。
最后判断堆是否为空即可，因为堆中维护的是\(m\)天后竹子高度会\(<h_i\)的竹子，所以堆空即代表所有竹子高度都\(\ge h_i\)。
时间复杂度\(O((n+mk)\log n\log mx)\)，其中\(mx\)表示\(\max\limits_{1\le i\le n} h_i+a_im\)（二分的上界）。
代码
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
int read(){
register int x = 0;
register char f = 1, ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 0;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return f ? x : -x;
}
int n, m, k, c[100005];
long long p, a[100005], h[100005], l = 0, r, mid, ans;
struct node{
int day, id;
bool operator < (const node &b) const {
return day > b.day;
}
};
struct Heap{
node h[200005];
int sz;
void clear(){ sz = 0; }
bool empty(){ return !sz; }
void push(node x){ h[++sz] = x, std :: push_heap(h + 1, h + 1 + sz); }
node pop(){ return std :: pop_heap(h + 1, h + 1 + sz), h[sz--]; }
node top(){ return h[1]; }
}H;
bool check(long long x){
H.clear(), memset(c, 0, sizeof c);
for (register int i = 1; i <= n; ++i)
if (x - a[i] * m < h[i]) H.push((node){x / a[i], i});
for (register int i = 1; !H.empty() && i <= m; ++i)
for (register int j = 1; !H.empty() && j <= k; ++j){
node u = H.pop();
if (u.day < i) return 0;
++c[u.id];
if (x + c[u.id] * p - a[u.id] * m < h[u.id])
H.push((node){(x + c[u.id] * p) / a[u.id], u.id});
}
return H.empty();
}
int main(){
n = read(), m = read(), k = read(), p = read();
for (register int i = 1; i <= n; ++i)
h[i] = read(), a[i] = read(), r = std :: max(r, h[i] + a[i] * m);
while (l <= r) check(mid = l + r >> 1) ? ans = mid, r = mid - 1 : l = mid + 1;
printf("%lld", ans);
}
|
