lowsfish

题目大意：给出\(n(n<10000.n\ mod\ 2=0)\)个盒子，每个盒子\(i\)里面有\(w_i\)个白球，\(b_i\)个黑球\((w_i+b_i=m)\)。要求把这\(n\)个球分成两组，每组\(\frac{n}{2}\)个盒子。要求两组里面要么黑球个数都严格大于白球个数，要么白球个数都严格大于黑球个数。定义\(m1\)为第一堆里面个数较多的球所占该堆总球数的比例，\(m2\)同样。最大化\(min(m1,m2)\)，无解输出No solution

不可做题！

随机爬山爬爬爬！

初始随便分组，然后每次随机从每组选一个元素，如果交换后更优就交换

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
const int MAXN = 10000 + 5;
const int MAXT = 50000 + 5;
using std::swap;
using std::min;
using std::max;
int n, m;
int w[MAXN], b[MAXN];
double ans = 0.0;
int a1[MAXN >> 1], a2[MAXN >> 1];
void climb_mountains() {
	int sumw1 = 0, sumb1 = 0, sumw2 = 0, sumb2 = 0;
	for (int i = 0; i < n; ++i) {
		if(i & 1) a1[i >> 1] = i, sumw1 += w[i], sumb1 += b[i];
		else a2[i >> 1] = i, sumw2 += w[i], sumb2 += b[i];
	}
	double tans = min((double)sumw1 / (sumw1 + sumb1), (double)sumw2 / (sumw2 + sumb2));
	for (int T = 0; T < MAXT; ++T) {
		int t1 = rand() % (n >> 1), t2 = rand() % (n >> 1);
		int tsumw1 = sumw1 + w[a2[t2]] - w[a1[t1]], tsumb1 = sumb1 + b[a2[t2]] - b[a1[t1]];
		int tsumw2 = sumw2 - (w[a2[t2]] - w[a1[t1]]), tsumb2 = sumb2 - (b[a2[t2]] - b[a1[t1]]);
		double t = min((double)tsumw1 / (tsumw1 + tsumb1), (double)tsumw2 / (tsumw2 + tsumb2));
		if (t > tans) {
			tans = t;
			sumw1 = tsumw1;
			sumb1 = tsumb1;
			sumw2 = tsumw2;
			sumb2 = tsumb2;
			swap(a1[t1], a2[t2]);
		}
	}
	if (tans > 0.5) ans = max(ans, tans);
}
int main() {
	srand(233333);
	while (scanf("%d%d", &n, &m) != EOF) {
		ans = 0.0;
		int sumw = 0, sumb = 0;
		for (int i = 0; i < n; ++i) {
			scanf("%d%d", w + i, b + i);
			sumw += w[i];
			sumb += b[i];
		}
		if (sumw == sumb) {
			puts("No solution");
			continue;
		}
		bool flag = 0;
		if (sumw < sumb) swap(w, b), swap(sumw, sumb), flag = 1;
		for (int i = 0; i < 5; ++i) climb_mountains();
		if (ans == 0.0) puts("No solution");
		else printf("%c %.2f\n",flag ? 'B' : 'W', ans * 100.0);
	}
	return 0;
}

然而这题数据弱的一比。。随机分组，随机十次就过了。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
const int MAXN = 10000 + 5;
const int MAXT = 50000 + 5;
using std::swap;
using std::min;
using std::max;
int n, m;
int w[MAXN], b[MAXN];
double ans = 0.0;
int a1[MAXN >> 1], a2[MAXN >> 1];
void climb_mountains() {
	int sumw1 = 0, sumb1 = 0, sumw2 = 0, sumb2 = 0;
	for (int i = 0; i < n; ++i) {
		if(i & 1) a1[i >> 1] = i, sumw1 += w[i], sumb1 += b[i];
		else a2[i >> 1] = i, sumw2 += w[i], sumb2 += b[i];
	}
	double tans = min((double)sumw1 / (sumw1 + sumb1), (double)sumw2 / (sumw2 + sumb2));
	for (int T = 0; T < MAXT; ++T) {
		int t1 = rand() % (n >> 1), t2 = rand() % (n >> 1);
		int tsumw1 = sumw1 + w[a2[t2]] - w[a1[t1]], tsumb1 = sumb1 + b[a2[t2]] - b[a1[t1]];
		int tsumw2 = sumw2 - (w[a2[t2]] - w[a1[t1]]), tsumb2 = sumb2 - (b[a2[t2]] - b[a1[t1]]);
		double t = min((double)tsumw1 / (tsumw1 + tsumb1), (double)tsumw2 / (tsumw2 + tsumb2));
		if (t > tans) {
			tans = t;
			sumw1 = tsumw1;
			sumb1 = tsumb1;
			sumw2 = tsumw2;
			sumb2 = tsumb2;
			swap(a1[t1], a2[t2]);
		}
	}
	if (tans > 0.5) ans = std::max(ans, tans);
}
int main() {
	srand(233333);
	while (scanf("%d%d", &n, &m) != EOF) {
		ans = 0.0;
		int sumw = 0, sumb = 0;
		for (int i = 0; i < n; ++i) {
			scanf("%d%d", w + i, b + i);
			sumw += w[i];
			sumb += b[i];
		}
		if (sumw == sumb) {
			puts("No solution");
			continue;
		}
		bool flag = 0;
		if (sumw < sumb) swap(w, b), swap(sumw, sumb), flag = 1;
		for (int i = 0; i < 5; ++i) climb_mountains();
		if (ans == 0.0) puts("No solution");
		else printf("%c %.2f\n",flag ? 'B' : 'W', ans * 100.0);
	}
	return 0;
}