CF505E 题解

CF505E 题解

$\text{Description}$

给定 $n,m,k,p$,给定两个序列 $\{h_n\}$ 和 $\{a_n\}$,接下来你要执行 $m$ 轮操作:

  1. 进行 $k$ 次特殊操作,每次特殊操作可以选择一个数 $i\in[1,n]$,然后使得 $h_i\gets \max(h_i-p,0)$;
  2. 对于所有 $i\in[1,n]$,使得 $h_i\gets h_i+a_i$。

现在你需要使得最后 $\max\limits_{1\le i\le n}\{h_i\}$ 最小。

$\text{Solution}$

首先最小化最大值这种问题很容易让我们想到二分答案,于是我们将问题转换为:是否存在一种操作方式,使得最后所有 $h_i<H$。

然后发现这个 $h_i$ 必须是非负的,所以它会使得这个贪心过程比较困难。

考虑再进行一次转换:存在一个满足 $\forall i\in[1,n],h’_i\ge h_i$ 的序列 $\{h’_ n\}$ ,存在一种操作方式使得最终 $\forall i\in[1,n],h’_n=H$。为什么这个和上面的问题是等价的呢?我们找出不同点:$h’_i\ge h_i,(last)h’_i=H$,发现如果存在一种操作方式使得这个条件满足的话,那么将这个操作方式应用在 $\{h_n\}$ 上后,就一定有 $(last)h_i\le H$。

我们接着思考:如果存在一个满足条件的初始序列,经过一种操作方式后使得最终序列里的数都等于 $H$,那么我们将操作方式反过来做一遍(顺序相反,加变减,减变加),就可以得到一个满足条件的初始序列。那么我们又进行了一个转换:

给定一个序列 $\{h’_ n\}$,你需要执行 $m$ 轮操作:

  1. 将所有 $i\in[1,n]$ 都执行 $h’_i\gets h’_i-a_i$;
  2. 进行 $k$ 次特殊操作,每次特殊操作可以选择 $i\in [1,n]$,然后执行 $h’_i\gets h’_i+p$。

那么怎样一个操作方式是合法的呢?它需要满足任意时刻不存在一个 $i\in[1,n]$ 使得 $h’_i<0$,这是因为 $h_i$ 非负。除此之外,还要满足最后时刻 $\forall i\in[1,n]$,都有 $h’_i\ge h_i$。

考虑到若有一个 $i$ 满足 $H-m\cdot a_i\ge h_i$,由于 $h_i$ 非负,所以这个 $i$ 是永远满足条件的,不需要去管。

考虑这么一个贪心:我们每次优先选择最快要变为负数的 $i$,然后给它加 $p$。在此基础上,我们维护一个数被加了多少次 $p$,记之为 $c_i$,维护一个小根堆,其以最早变为负数的天数前一天为关键字($\lfloor\frac{(H+c_i)}{a_i}\rfloor$,注意 $h’_i$ 是可以为 $0$ 的)。每次特殊操作我们取堆顶进行一次特殊操作,然后判断其在经过这一次特殊操作后,是否可以再也不用特殊操作也能在最终满足 $h’_i\ge h_i$,若不是,则要将其再次插入堆中。最后只需判断堆是否为空即可。

几个细节需要注意,任何要取堆顶或弹出堆顶时候都要判断堆是否为空,还有判断其是否需要再次插入堆中时要记得加上 $c_i\cdot p$。

$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#define REG register
#define LL long long
#define MAXN 100005
using namespace std;
inline void read(LL& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}

LL n,m,k;
LL p,h[MAXN],a[MAXN];

struct Node{
int Day,Id;
bool operator<(const Node& a)const{return Day>a.Day;}
};

priority_queue<Node> PQ;
int Cnt[MAXN];

inline bool Chk(LL mid){
memset(Cnt,0,sizeof Cnt);
while(PQ.size()) PQ.pop();
for(REG int i=1;i<=n;++i)
if(mid-m*a[i]<h[i]) PQ.push((Node){mid/a[i],i});
for(REG int i=1;PQ.size()&&i<=m;++i)
for(REG int j=1;PQ.size()&&j<=k;++j){
Node Now=PQ.top();PQ.pop();
if(Now.Day<i) return 0;
++Cnt[Now.Id];
if(mid+p*Cnt[Now.Id]-m*a[Now.Id]<h[Now.Id])
PQ.push((Node){(mid+p*Cnt[Now.Id])/a[Now.Id],Now.Id});
}
return PQ.empty();
}

inline void Work(){
read(n),read(m),read(k),read(p);
LL l=1,r=0,mid,ans=0;
for(REG int i=1;i<=n;++i){
read(h[i]),read(a[i]);
r=max(r,h[i]+m*a[i]);
}
while(l<=r){
mid=(l+r)>>1;
if(Chk(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld\n",ans);
}

int main(){Work();}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×