Codeforces Round #286 (Div. 2) E. Mr. Kitayuta vs. Bamboos（二分，思维）

题目链接

题面：

题意：

给定n棵竹子, 每棵竹子初始hi, 每天结束时长ai, 共m天, 每天可以砍k次竹子，每次砍掉p，可以重复选择一棵竹子砍（在当天竹子增长之前砍掉）, 若不足p则变为0, 求m天后竹子最大值 的最小值。

因为是“最小化最大值”，容易想到二分答案。设二分值为mid，我们要判断是否能使最终所有竹子的高度都≤mid。如果从前往后安排每一天，会发现很难找到一种固定的贪心策略，来确定当天砍哪些竹子。

换个角度。考虑最后一天，所有竹子会长高ai米。那么在最后一天竹子开始生长之前，第 i 个竹子不能高于 mid−ai 米。

如果我们在最后一天不砍第 i 个竹子，那么在倒数第二天竹子开始生长之前，第 i 个竹子不能高于mid − 2 * ai米。

如果在最后一天砍了第i个竹子，设砍了x次，那么在倒数第二天竹子开始生长之前，第 i 个竹子不能高于 mid + p * x − 2 * ai米。

以此类推。

按照这种“时光倒流”的想法：

每个竹子初始高度为mid，每天高度会减少ai，我们每用一次砍伐机会可以使其高度增加p。
这里的“高度”，代表的实际含义是：如果之后按照我们确定的这种方式砍伐（因为我们在时光倒流，所以之后的砍伐方式都已经确定了），那么（在正向时间中）当前时刻这根竹子的高度应不高于多少，才能使得最终高度不超过mid。
根据这个含义，我们要做的就是保证在整个时光倒流的过程中，每根竹子的“高度”始终不能为负。因为一但“高度”为负，意味着要求（正向时间中）高度不得高于一个负数，这显然是不可能的。

通过时光倒流，确定出的“高度”：即，每个时刻，实际高度不得高于多少。

于是，通过时光倒流，问题转化为：每个竹子初始高度为mid，每天高度会减少ai，我们每用一次砍伐机会可以使其高度增加p。在m天中要保证所有竹子高度始终非负，且m天结束后每个竹子高度要≥hi。

这样转化的好处是，我们避免了在正向时间中，一次砍伐减少的高度不足p的问题；转化后，每次砍伐操作一定能使当前竹子高度增加p，与初始高度无关。

转化后，这是经典的贪心问题。我们计算出每个竹子，在不被砍伐的情况下，每天减少ai米，最多能坚持几天。以这个天数作为关键字，把所有坚持m天后小于hi的竹子扔进一个小根堆里面（这些竹子说明还需要拔高）。依次完成 m * k 次砍伐（拔高），每次取出堆顶，如果其能坚持的天数小于当前进行的第 i 轮砍伐（拔高），直接返回false（也就是说贪心的进行，至少需要第 i 天才能拔高这跟竹子，但是其只能坚持少于 i 天大于等于0）。否则对其砍一刀（使其高度增加p）。增加高度后，若其能坚持到m天后且高度大于等于hi，则不再放入堆中，否则更新它能坚持的天数，放入堆中。

时间复杂度 O（（n + k * n） * logn * log inf）
logn 来自于小根堆，log inf 来自于二分。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define pr make_pair
#define pb push_back
#define ui unsigned int
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x)  (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define forhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1000000007;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxn=100100;
const int maxm=100100;
const int up=100000;struct node
{ll day,id;node(){}node(ll a,ll b){day=a,id=b;}friend bool operator < (const node &a,const node &b){return a.day>b.day;}
};ll n,m,k,p;
ll cnt[maxn],h[maxn],a[maxn];
priority_queue<node>q;bool check(ll mid)
{while(q.size()) q.pop();memset(cnt,0,sizeof(cnt));for(int i=1;i<=n;i++){if(mid-m*a[i]<h[i])q.push(node(mid/a[i],i));}ll day,id;for(int i=1;i<=m;i++){for(int j=1;j<=k;j++){if(q.size()==0) return true;day=q.top().day;id=q.top().id;q.pop();if(day<i) return false;cnt[id]++;if(mid+cnt[id]*p-m*a[id]<h[id])q.push(node((mid+cnt[id]*p)/m,id));}}if(q.size()) return false;else return true;
}int main(void)
{cin>>n>>m>>k>>p;for(int i=1;i<=n;i++)scanf("%lld%lld",&h[i],&a[i]);ll l=0,r=1e13,ans=0;while(l<=r){if(check(tmid)) ans=tmid,r=tmid-1;else l=tmid+1;}cout<<ans<<endl;return 0;
}