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

一眼贪心题。

注意到：

如果 $x>y$ 那么第一个回合就能超过。
如果 $x+n\le y$ 那么无论如何无法超过。
否则 $x+n>y$ 也就是说只要等待时间够长就能超过。

那么该按照什么顺序攻占城堡呢？

城堡（以下简称“塔”）的费用越小越好：从加兵力的角度看，塔的费用越小，那么你花费越小，并且你能更快地攒够兵力，也就更快地能让塔工作。

因此，可以将塔的花费按照从小到大排序，依次占领，只要能占就占。

attention：如果此时的

x+k>y

了，也就是说可以现在就放弃继续开塔，直接蹲兵力，此时是可以直接算出还要多久才能超过对手的，所以要把这些满足

x+k>y

的情况考虑进去，而不是开完所有塔才是最好的！

于是：上代码！

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int cal(int x,int y){return (x+y-1)/y;}
signed main(){
	int T;cin>>T;
	while(T--){
        int n,x,y,a[N];
        cin>>n>>x>>y;
    	for(int i=1;i<=n;i++)cin>>a[i];
        if(x+n<=y){puts("-1");continue;}
        if(x>y){puts("1");continue;}
    	sort(a+1,a+n+1);
    	int rlt=0x3f3f3f3f,turns=0;
    	int me=0,other=0;
    	for(int i=1;i<=n;i++){
    		if(x>y)rlt=min(rlt,turns+cal(other-me+1,x-y));
    		int t=max(0ll,cal(a[i]-me,x));
    		turns+=t+1;
    		other+=(t+1)*y;
    		me+=(t+1)*x-a[i];
    		x++;
    	}
        rlt=min(rlt,turns+cal(other-me+1,x-y));
    	cout<<rlt<<endl;
    }
	return 0;
}

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

文章操作

注意到：

那么该按照什么顺序攻占城堡呢？

于是：上代码！

相关推荐

评论

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