CodeForces 1250G [贪心]_codeforce 1250g

题目链接:https://codeforces.com/contest/1250/problem/G

解题思路:

题目的另一个意思就是每次按动reset意思就是原来的sa,sb(表示a,b现在的积分)变成了sa = sa -  min(sa,sb),sb = sb - min(sa,sb),根据这一的性质我们就可以都得到一个结论就是，当只执行到第i轮时，最后一次按下了reset是在第k轮，那么这是sa[i] = pre_a[i] - min(pre_a[k],pre_b[k]),sb[i] = pre_b[i] - min(pre_a[k],pre_b[k])。pre[]表示数组前缀和，再记w[k] = min(pre_a[k],pre_b[k]

m 是题中最大积分的限制

那么如果人想在第i轮赢得话，必须就要满足存在k使得pre_a[i] - m < w[k] <= pre_b[i] - m, k < i。根据这个式子就可以去判断如果到了第i轮是否有可以取胜的策略，那么接下来我们就只要保证人到第i轮之前积分不会爆m就可以了，这个就直接贪心就好了，因为已经确定了在第几轮的时候可以赢了。

#include<bits/stdc++.h>
using namespace std;
const int mx = 2e5+5;
const int mod = 1e9 + 7; 
typedef long long ll;
int n,m;
int a[mx],b[mx],ans[mx];
ll sa[mx],sb[mx];
ll w[mx];
int get_id() {
	for (int i=1;i<=n;i++) {
		ll L = sa[i] - m;
		ll R = sb[i] - m;
		int l = upper_bound(w+1,w+i,L) - w;
		int r = upper_bound(w+1,w+i,R) - w;
		if (l < r) {
			//cout << l << " " << i << endl;
			return l;
		}
		w[i] = min(sa[i],sb[i]);
	}
	return -1;
}
int solve(int id) {
	ll now1 = 0,now2 = 0;
	int siz = 0;
	for (int i=1;i<id;i++) {
		now1 += a[i];
		now2 += b[i];
		if (now1 + a[i+1] >= m) {
			ll mi = min(now1,now2);
			ans[siz++] = i;
			now1 -= mi,now2 -= mi;
			if (now1 + a[i+1] >= m) return 0;
		}
	}
	ans[siz++] = id;
	return siz;
}
bool check() {
	for (int i=1;i<=n;i++)
		if (sa[i]<m&&sb[i]>=m)
			return 1;
	return 0;
}
int main(){
	int t;
	scanf("%d",&t);
	while (t--) {
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++) {
			scanf("%d",a+i);
			sa[i] = sa[i-1] + a[i];
		}
		for (int i=1;i<=n;i++) {
			scanf("%d",b+i);
			sb[i] = sb[i-1] + b[i];
		}
		if (check()) {
			puts("0\n");
			continue;
		}
		int id = get_id();
		int siz = solve(id);
		if (!siz || id == -1) {
			puts("-1");
			continue;
		}
		printf("%d\n",siz);
		for (int i=0;i<siz;i++) {
			printf("%d%c",ans[i],i==siz-1?'\n':' ');
		}
	}
	return 0;
}