题解 CF505E 【Mr. Kitayuta vs. Bamboos】
StudyingFather
2019-11-30 14:14:38
看到“最大值最小”，首先想到二分答案。
但存在一个问题：高度是非负的，处理负高度这个问题会稍微有些棘手（当然也不是不能实现）。
如果我们让时间倒流呢？我们会看到这样一种景象：刚开始所有竹子的高度都为 $x$，竹子每天高度会下降 $a_i$，而我们的操作呢，则是将选定的竹子拔高 $p$。
我们的目标是让任何时刻竹子的高度都非负，而倒推到最开始的时候，第 $i$ 个竹子的高度不能低于 $h_i$。
这样我们就避开了可能的负高度的问题。
针对上面的场景，我们可以贪心解决：如果一个竹子有高度变为负的风险，我们就把它拔高。假如不存在这样的竹子，我们则选择最终高度可能会低于 $h_i$ 的竹子。
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct node
{
long long d;
int id;
bool operator<(const node&a)const
{
return d>a.d;
}
};
long long a[100005],h[100005],t[100005],n,m,k,p;
bool check(long long x)
{
priority_queue<node> q;
for(int i=1;i<=n;i++)
{
t[i]=x;
if(x-a[i]*m<h[i])q.push({x/a[i],i});
}
for(int i=1;i<=m;i++)
for(int j=1;j<=k;j++)
{
if(q.empty())return true;
int d=q.top().d,id=q.top().id;
q.pop();
if(d<i)return false;
t[id]+=p;
if(t[id]-a[id]*m<h[id])q.push({t[id]/a[id],id});
}
return q.empty();
}
int main()
{
cin>>n>>m>>k>>p;
for(int i=1;i<=n;i++)
cin>>h[i]>>a[i];
long long l=0,r=1ll<<60;
while(l<r)
{
long long mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
```