目录
@description@
n 个竹子，第 i 个竹子初始高度 hi，在每天结束时将长高 ai。
一共 m 天，每天可以砍伐 k 次，可以多次砍伐同一个竹子。如果砍伐的竹子当前高度 h，则砍后变为 max(0, h – p)。
问 m 天之后最高的竹子的高度最小是多少。
@solution@
考虑第 i 个竹子如果在第 j 天被砍了 \(c_{i,j}\) 次，则最后剩下的高度应为：
\[\max\{h_i + m\times a_i – \sum_{k=1}^{m}c_{i,k}, \ \max_{j=1}^{m}\{(m-j+1)\times a_i – \sum_{k=j+1}^{m}c_{i,k}\}\}
\]
根据砍伐的定义，这是易证的。
我们不妨二分答案 x，前面包含 hi 的式子暴力 O(n) 判断。后面的式子如果暴力判断是 O(nm) 的复杂度。
注意到 k 很小，也就是说总的砍伐数量只有 O(mk) 次，远远小于 O(nm)。
我们不妨只记录对于每棵竹子而言的有效砍伐，使用 m 个队列从后往前进行模拟，就可以做到 O(mk + n) 的判断时间复杂度。
总时间复杂度 O((mk + n)log A)。
@accepted code@
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pairconst int MAXM = 5000;
const int MAXN = 100000;int n, m, k;
ll a[MAXN + 5], h[MAXN + 5], p;
queue<pii>que[MAXM + 5];
bool check(ll x) {
for(int i=1;i<=m;i++) {
while( !que[i].empty() )
que[i].pop();
}for(int i=1;i<=n;i++) {
ll s = x / a[i] + 1;
if( s <= m ) que[s].push(mp(i, 0));
}for(int i=1,c=0;i<=m;i++,c+=k) {
while( !que[i].empty() ) {
if( c ) c--; else return false;pii f = que[i].front(); que[i].pop(); f.se++;
ll s = (f.se*p + x) / a[f.fi] + 1;
if( s <= m ) que[s].push(f);
}
}ll s = 0;
for(int i=1;i<=n;i++)
s += (max(a[i]*m + h[i] - x, 0LL) + p - 1) / p;
return s <= m*k;
}int main() {
scanf("%d%d%d%lld", &n, &m, &k, &p);
for(int i=1;i<=n;i++) scanf("%lld%lld", &h[i], &a[i]);ll le = 0, ri = 0;
for(int i=1;i<=n;i++)
ri = max(ri, h[i] + m*a[i]);while( le < ri ) {
ll mid = (le + ri) >> 1;
if( check(mid) ) ri = mid;
else le = mid + 1;
}
printf("%lld\n", ri);
}
@details@
一开始本来想写线段树结果发现会 T，最后还是换成了队列模拟。
注意开 long long 的问题。有些地方虽然合法在 int 范围内，但不合法的情况会炸。
