1.算法:
二分+贪心
2.思路:
首先我们二分出一个值x,对于这个值就行check...怎么check呢?
一个很显然的东西,假如我的开始值是x,且我x-a[i]*m>=h[i]这种值是不可能用到的.
其次我们假设我们的初始值是x,且都要用到,那么我肯定是选变成负数步数最少的优先,因为我想让我每次减少的p尽可能的多.
然后就可以直接用优先队列模拟维护了.
3.代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
ll a[N],h[N];
ll n,m,k,p;
struct Q{
ll tot,ai,num,id;
friend bool operator<(const Q &A,const Q &B)
{
return A.num>B.num;
}
};
bool check(ll x)//枚举那个最大值最小的值并验证是不是可行.
{
priority_queue<Q>q;
for(int i=1;i<=n;i++)
{
if(x-a[i]*m<h[i]) q.push({x,a[i],(x)/a[i],i});
}
for(int i=1;i<=m&&q.size();i++)//m轮
{
for(int j=1;j<=k&&q.size();j++)//k次抬高
{
auto temp=q.top();q.pop();
int id=temp.id;
if(temp.tot-temp.ai*i<0) return false;
temp.tot+=p;temp.num=(temp.tot)/temp.ai;
if(temp.tot-temp.ai*m<h[id]) q.push(temp);
}
}
while(q.size())
{
auto temp=q.top();
q.pop();int id=temp.id;
if(temp.tot-temp.ai*m<h[id]) return false;
}
return true;
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
for(int i=1;i<=n;i++) scanf("%lld%lld",&h[i],&a[i]);
ll l=1,r=1e18,ans=1e18;
while(l<=r)
{
ll mid=(l+r)>>1;
if(check(mid))
{
r=mid-1;
ans=min(ans,mid);
}
else
{
l=mid+1;
}
}printf("%lld\n",ans);
return 0;
}