noip模拟测试34

noip模拟测试34

t3 密州盛宴

由于讲题时没有组织好语言去讲，中午睡觉的时候想了想赶紧写篇题解向乡亲们（雾）谢罪（动动的代码在判断-1的地方错了，请认准唯一正解）
很显然的是前面的0越多越好，这样其他人可以不吃1，尽量多的吃0，另外也可以保证东坡每时每刻都有1吃
可以考虑一种特殊情况，就是其他人都尽量把0都吃完再吃一，此时一定有解，但是显然多了很多不必要的交换操作，也就是说其他人也可以吃1，不一定吃0
举个例子：
1 1 1 1 1 1 1 0 0 0
这种情况下我们先让其他人吃 0， 可以得到该序列
1 0 1 0 1 0 1 1 1 1
最多的交换了6次
但是由于其他人也可以吃1,并且可以吃两个1,所以我们不妨把这个序列做出该变化
1 1 1 1 1 0 1 0 1 0
这样我们只交换了两次就可以完成
也就是其中我们有四次的交换是多余的，因为在前面我们可以先吃两个1，而两种方案差的交换次数也是很显然，及1的个数减去0的个数
代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
inline int read () {
	int x = 0, f = 1; char ch = getchar();
	for (;!isdigit(ch); ch = getchar()) if (ch == ‘-‘) f = -1;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - ‘0‘;
	return x * f;
}
const int maxn = 1e6 + 50;
int n, m;
char S[maxn], now[maxn];
long long t;
long long ans = 0;
signed main () {
	freopen ("meal.in", "r", stdin);
	freopen ("meal.out", "w", stdout);
	while (1) {
		n = read(), m = read();
		if (n == 0 && m == 0) return 0;
		long long cnt0 = 0, cnt1 = 0;
		ans = 0;
		register int len;
		register int js0 = 0, js1 = 0;
		register int maxx = -0x3f3f3f3f;
		for (register int i = 1; i <= m; i++) {
			scanf ("%s", now + 1);
			t = read();
			len = strlen (now + 1);
			js0 = js1 = 0;
			maxx = -0x7fffffff;
			maxx = max (js0 - js1, maxx);
			for (register int j = 1; j <= len; j++) {
				if (now[j] == ‘0‘) {
					maxx = max (js1 - js0, maxx);
					++js0;
				} else {
					++js1;
				}
			}
			if (js0 == 0) {
				cnt0 += js0 * t, cnt1 += js1 * t;
				continue;
			}
			ans = max (ans, cnt1 - cnt0 + maxx);
			ans = max (ans, cnt1 - cnt0 + (js1 - js0) * (t - 1) + maxx);
			cnt0 += js0 * t, cnt1 += js1 * t;
		}
		if (cnt0 > cnt1) {
			puts("-1");
		} else if (cnt0 == cnt1) {
			cout<<max((ans - 1), 0ll)<<endl;
		} else {
			cout<<max(0ll, (ans - 1 - (cnt1 - cnt0)))<<endl;
		}
	}
	return 0;
}

noip模拟测试34

原文：https://www.cnblogs.com/hzoi-liujiahui/p/14010650.html