P11467题解

考虑贪心，每次开所耗兵力最小的塔，当

x>y

时判断是否再开新的塔。

证明

假设每次不是开所耗兵力最小的塔，又因为只能当

x>y

时 t1e 同学的兵力才能超过对面。则所让

x>y

时所需的回合数一定大于每次开所耗兵力最小的塔所需的回合数，故假设不成立。

判断有无解

显然只有当

x+n>y

时 t1e 同学的兵力才能超过对面。当

x+n \le y

时 t1e 同学的兵力永远无法超过对面。

Code

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,x,y,T,a[300005];
signed main(){
	cin>>T;
	while(T--){
		int ans=1e18;
		cin>>n>>x>>y;
		int army=0,num=0,add=x;//army 为现有兵力，num为回合数，add 为每回合的产兵数
		for(int i=1;i<=n;i++) cin>>a[i];
		if(x>y) {
			cout<<1<<endl;
			continue;
		}
		if(x+n<=y){
			cout<<-1<<endl;
			continue;
		}
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++){
			num=max(num+1,(int)ceill((a[i]-army)*1.0/add)+1);
			int cnt=add*num+army;
		    add++,army=cnt-a[i]-add*num;
			if(add>y)ans=min(ans,army/(y-add)+1);//判断是否再多开塔
		}
		cout<<ans<<endl;
	}
}

题解：P11467 网瘾竞赛篇之 generals 大法好

文章操作

P11467题解

证明

判断有无解

Code

相关推荐

评论

题解：P11467 网瘾竞赛篇之 generals 大法好