Studying Father's luogu blog

Studying Father's luogu blog

从零至灵,由壹达意

题解 CF505E 【Mr. Kitayuta vs. Bamboos】

posted on 2019-11-30 14:14:38 | under 题解 |

看到“最大值最小”,首先想到二分答案。

但存在一个问题:高度是非负的,处理负高度这个问题会稍微有些棘手(当然也不是不能实现)。

如果我们让时间倒流呢?我们会看到这样一种景象:刚开始所有竹子的高度都为 $x$ ,竹子每天高度会下降 $a_i$ ,而我们的操作呢,则是将选定的竹子拔高 $p$ 。

我们的目标是让任何时刻竹子的高度都非负,而倒推到最开始的时候,第 $i$ 个竹子的高度不能低于 $h_i$ 。

这样我们就避开了可能的负高度的问题。

针对上面的场景,我们可以贪心解决:如果一个竹子有高度变为负的风险,我们就把它拔高。假如不存在这样的竹子,我们则选择最终高度可能会低于 $h_i$ 的竹子。

#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;
}