自动搬运

查看原文

来自洛谷，原作者为

	szh_AK_all S挂分挂到被洛谷7级勾卡线|I can do all things

搬运于2025-08-24 22:55:21，当前版本为作者最后更新于2024-02-17 20:32:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

我们需要进行若干次操作，使得字符串 $s$ 的顺序对数量最大。每次操作可以将 $s$ 中相邻的两个值取反。

分析

由于 $s$ 只包含 $0$ 和 $1$，所以为了使顺序对数量最大，我们尽可能将 $1$ 放在末尾，将 $0$ 尽可能放在前面。可以发现，经过操作后，$0$ 或 $1$ 的数量会发生改变。所以，这也为我们后续的操作奠定了基础。

首先，我们将问题简化：我们可以让字符串 $s$ 末尾有任意数量的 $1$，开头有任意数量的 $0$，那么我们该如何分配 $1$ 和 $0$ 的数量，使得顺序对数量最大呢？

相信大家都明白这个道理吧：在周长相等的正方形与长方形中，正方形面积总比长方形大。为什么？因为正方形的边长相等，也就是差值为 $0$。

转换为数学逻辑就是：$x1\times x2$ 与 $y1\times y2$ 相比（$x1+x2=y1+y2$，为了方便起见，设 $x1\le x2,y1\le y2$），若 $x2-x1<y2-y1$，则 $x1\times x2>y1\times y2$；反之同理。

举个例子：若 $s$ 的长度为 $5$，则最优情况下 $s$ 中有两个 $0$，三个 $1$，或者有三个 $0$，两个 $1$。

清楚这个问题后，再来考虑题目。我们要尽可能让 $1$ 靠后，$0$ 考前，且 $1$ 的数量与 $0$ 的数量相差小，则我们由字符串的末尾像中间枚举，若枚举到的字符为 $0$，则使用一次操作；同理，再由字符串的开头像中间枚举，若枚举到的字符为 $1$，则使用一次操作。

枚举 $1$ 的情况时若枚举到的字符为 $0$，则使用一次操作，为什么这样可以保证字符串从中间到末尾都为 $1$ 呢？假设该字符前一个字符为 $0$，则两全其美，这两个字符都变为了 $1$；若前一个字符为 $1$，则在操作之后，前一个字符变为 $0$，但是不用担心，因为在下一轮的枚举中前一个字符又会变为 $1$。

Code

#include <bits/stdc++.h>
using namespace std;
int ans, a[200005];

int main() {
	string s;
	cin >> s;
	int n = s.size();
	for (int i = n - 1; i >= n / 2; i--) {
		if (s[i] == '0') {
			a[++ans] = i;
			s[i] = '1';
			if (s[i - 1] == '0')
				s[i - 1] = '1';
			else
				s[i - 1] = '0';
		}
	}
	for (int i = 0; i < n / 2; i++) {
		if (s[i] == '1') {
			a[++ans] = i + 1;
			s[i] = '0';
			if (s[i + 1] == '0')
				s[i + 1] = '1';
			else
				s[i + 1] = '0';
		}
	}
	long long o = 0;
	for (int i = 0; i < n; i++)
		if (s[i] == '1')
			o++;
	long long tmp = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '0')
			tmp += o;
		else
			o--;
	}
	cout << tmp << endl << ans << endl;
	for (int i = 1; i <= ans; i++)
		cout << a[i] << " ";
}

打字不易，请管理大大通过吧！也请各位点个赞！

另外附上赛事记录