题目链接

题面:

题意:

给定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;
}