题解十二：P13500 「Cfz Round 6」Kyu-kurarin

题意

一个正整数序列

a

，进行

s

次操作，每次将

k

个数增加

1

，求出最大的

s

使得序列中的每一项满足

a_i-s>0

。

思路

本题的答案显然具有单调性。所以，二分答案。

对于一个

s

，要判断它是否满足要求，我们就需要对原序列的每一项

a_i

进行判断：如果不满足

a_i-s > 0

，就需要增加

a_i

直到满足，并把这个增加量增加到一个变量

num

中。（显然，如果一项本身就满足条件便不需要增加。）最后，

num

就记录了使得整个序列满足条件的总增加量。由题意可知，

s

次操作最多可以增加

s \times k

次。若满足

num \le s \times k

则

s

符合题意，反之不符合。

CPP

bool check(ll s){
	ll num=0;
	for(ll i=1;i<=n;i++){
		num+=max((ll)0,s-a[i]+1);
		if(num>s*k) return false;
	}return true;
}

s-a[i]+1 的含义

由

a_i-s > 0

可以得出

a_i > s

时该项满足条件。

反过来，当

a_i \le s

时不满足条件，需要增加。显然把

a_i

增加到

s+1

就可以满足条件。而

s+1

与

a_i

相减的差（即

a_i

的“增加量”）便是

s-a_i+1

。（好像是句废话。）

若是该项本身就满足

a_i > s

，那么

s-a_i+1

的结果便是非正数。使用 max() 在该式与

0

中取最大值即可。

代码

CPP

1234567891011121314151617181920212223//1.38s / 8.14MB / C++17 O2
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,k,l,r=1e12,mid,ans,a[1000010];
bool check(ll s){
	ll num=0;
	for(ll i=1;i<=n;i++){
		num+=max((ll)0,s-a[i]+1);
		if(num>s*k) return false;
	}return true;
}
int main(){
	// freopen("ice4.in","r",stdin);
	cin>>n>>k;
	for(ll i=1;i<=n;i++) cin>>a[i];
	while(l<r){
		mid=(l+r)/2+1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}cout<<l;
	return 0;
}

题解十二：P13500 「Cfz Round 6」Kyu-kurarin

文章操作

题意

思路

代码

相关推荐

评论

题解十二：P13500 「Cfz Round 6」Kyu-kurarin