【Codeforces 505E】Mr. Kitayuta vs. Bamboos | Mrsrz's blog

贪心，二分答案

题目大意：

给定 $n$ 个竹子，每个竹子有初始高度 $h_i$，并会在每个晚上增加 $a_i$ 的高度。

一共有 $m$ 天，每天白天可以砍 $k$ 次，每次可以砍掉一棵竹子（可以重复砍） $p$ 的长度（如果剩下的长度不足 $p$ 则砍光为止）。

求 $m$ 天过后，最长的竹子最短能够是多少。

题解：

考虑二分答案。

每次判断答案可行性。

我们倒着考虑，令当前二分的答案为 $H$，则令最后一天结束时的高度都为 $H$。

然后就相当于，每天竹子的高度会先减少 $a_i$，然后再选择 $k$ 根竹子，将其拔高 $p$。注意先后。

最后，要求每个竹子的高度都大于等于它原来的 $h_i$，则说明可行。并且中途不能有竹子高度小于 $0$。

贪心，计算出每棵竹子到什么时候，高度会变成负数。每次取变成负数最快的那个，将其拔高。

用堆维护。

如果一棵竹子在某次拔高后（或一开始），在规定时间内永远都不低于 $h_i$ 则不插回去。

正确性的话，我们肯定先得处理掉那些会变成负数的，而且越早的显然要越早处理掉。然后再把会低于 $h_i$ 的变高。变到满足条件就不再理会它了。

时间复杂度 $O(mk\log n\log w)$。

Code：

#include<iostream>
#include<queue>
using namespace std;
typedef long long LL;
const int N=1e5+6;
int n,m,k,p,h[N],a[N];
struct data{
    int id,s,t;
    LL H;
    inline bool operator<(const data&rhs)const{
        return t>rhs.t;
    }
    inline void update(int tim){
        H-=(tim-s)*(LL)a[id];
        s=tim;
        t=tim+H/a[id];
    }
};
priority_queue<data>q;
bool check(LL H){
    while(!q.empty())q.pop();
    for(int i=1;i<=n;++i)if(H-(LL)m*a[i]<h[i]){
        data s=(data){i,1,0,H};
        s.update(1);
        q.push(s);
    }
    for(int T=1;T<=m;++T)
        for(int x=1;x<=k;++x){
            if(q.empty())return 1;
            if(q.top().t<=T)return 0;
            data t=q.top();
            q.pop();
            t.H+=p;
            t.update(T);
            if(t.H-(LL)a[t.id]*(m-T+1)<h[t.id])q.push(t);
        }
    return q.empty();
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>p;
    for(int i=1;i<=n;++i)
        cin>>h[i]>>a[i];
    LL l=0,r=1e18,ans=1e18;
    while(l<=r){
        const LL mid=l+r>>1;
        if(check(mid))r=(ans=mid)-1;else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}