恐怕要继续掉分了……没经过证明的贪心绝对不能用啊。

A

水题，约分即可。

B

输入一个长度为 $n$ 的序列，每次可以选一个长度不超过 $n$ 的区间打乱，求使他有序的最小步数。

显然，若原来有序答案是 $0$, 若头/尾在正确的位置上答案是 $1$, 那么否则答案是不是就是 $2$ 了呢？

其实不是，还要考虑 $1$ 在 $n$ 且 $n$ 在 $1$ 的情况，这样没法一次使头/尾归位，所以需要三次操作。

因为没考虑到最后一个情况，所以 WA 了一发。

其实前面的情况的证明中就涉及了一次要让头/尾中至少一个归为，所以当然应该考虑不能归为的情况。

C

看了题大概知道是小模拟，先搞个栈处理一遍再处理通向两边的再处理回来的。因为不想写小模拟所以先过。

D

每次可以移动一个 $1$, 移动代价是移动的距离，将 $1$ 全移动到 $0$ 的位置上的最小代价是多少？

模拟了几个小样例觉得不能穿越，所以天真的以为就是从中间分开，然后必然往两边跑，但这个想法实际上样例都过不了，居然写完了以后才发现这一点。

然后又去想着其它的贪心，就是一块向两边拓展，想了想似乎没有问题，因为如果一定要到另一边才行的话那后面的必然会到另一边的。

但实际上这个做法是错误的，反例如下：

30
0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 1 

正确输出是 $52$，而我呢吧的做法输出是 $60$, 因为最右边那一段往右边移动更近，而实际上左边多使用一格可以使前面减少的更多。而我的所谓证明错在它根本没有证明，它只是考虑跨越的情况而已，而没有考虑整体往一边多出一点会更优。

正确做法是一个挺好做的 dp。设 $f_{i,j}$ 是用 $i$ 个 $0$ 和 $j$ 个 $1$ 要移动的最少步数，那么 $f_{i,j} = \min\{f_{i-1, j}, f_{i-1,j-1} + |a_i - b_j|\}$, 其中 $a$ 和 $b$ 中存的分别是 $0$ 和 $1$ 的下标们。

这样是对的因为加入一个 $0$ 或把当前最后一个 $1$ 移动到最后一个 $0$ 的构造方案可以构造出所有的移动方案。

代码。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
const int N = 5005;
int n, x, f[N][N];
std::vector<int> a, b;
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &x);
		if(x == 0) a.push_back(i);
		else b.push_back(i);
	}
	memset(f, 0x3f, sizeof f);
	f[0][0] = 0;
	for(int i = 1; i <= (signed)a.size(); i++)
		for(int j = 0; j <= std::min((signed)b.size(), i); j++) {
			f[i][j] = std::min(f[i-1][j], f[i][j]);
			if(j != 0) f[i][j] = std::min(f[i][j], f[i-1][j-1] + std::abs(a[i-1] - b[j-1]));
	}
	printf("%d", f[a.size()][b.size()]);
	return 0;
}

根据 CVR 数据， 我其实第一次贪心 WA 了之后转 dp 还是来得及的……

所以未经证明的贪心千万别用，用了之后 WA 了也赶紧回头吧。