本文主要是介绍Codeforces 1250 G Discarding Game —— 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way/a>
题意：
现在你和一个机器人在比赛，共有n个回合，从1到n，每回合你会得到a[i]点值，机器人会得到b[i]点值，规则入下：
当有一个人的值大于等于k，那么这个人就会输掉比赛，另一个人赢，GG。但是如果两个人同时大于等于k，那么两个人都算输，GG
每一次你都可以重置你们的值，重置的意思就是你和电脑都减去你们两个人的最小值。
当第n回合结束时没分出胜负，GG。
现在问你是否能分出胜负，以及如果能分出胜负，最少的重置次数以及重置的是哪些回合。
题解：
这里很明显，越早结束越好，因为这样的重置次数最少。
那么我们只需要枚举最后一次重置的位置，然后再看之后是否可能，如果可能的话，我们首先检查一遍这里面是否有一直重置都无法胜利的情况，如果一定有答案，那么我们只需要贪心的在每次都要超出去的时候重置即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
ll a[N],b[N];
vector<int>vec;
int main()
{int n,t;ll k;scanf("%d",&t);while(t--){scanf("%d%lld",&n,&k);for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];for(int i=1;i<=n;i++)scanf("%lld",&b[i]),b[i]+=b[i-1];int f=0,now=1;for(int i=0;i<=n;i++){int p=lower_bound(a+i+1,a+1+n,min(a[i],b[i])+k)-a-1;if(p==i)continue;while(now<=p){if(a[now]-min(a[now-1],b[now-1])>=k)break;now++;}if(now<=p)break;if(b[p]-min(b[i],a[i])>=k){vec.clear();int pre=0;for(int j=1;j<=i;j++){if(a[j]-min(a[pre],b[pre])>=k)vec.push_back(j-1),pre=j-1;}if(i)vec.push_back(i);printf("%d\n",vec.size());for(auto j:vec)printf("%d ",j);printf("\n");f=1;break;}}if(!f)printf("-1\n");}return 0;
}这篇关于Codeforces 1250 G Discarding Game —— 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
