原题链接：https://codeforces.com/contest/1700/problem/F
题目大意
给你两个 2*n 的矩阵。上面只有 0 和
1。你每次操作能交换两个相邻位置上的数字。问你最少需要多少次操作才能把矩阵
1 转换成矩阵 2。
思路分析
一道需要仔细观察和猜结论的贪心题。
首先，如果两个矩阵 1 的数量不一样，无解。
然后，这个所谓的交换，可以直接看成 1 的移动。我们假设 1 的数量为
m。
然后你会发现，问题转化成了这样：有 m 个目标点和 m
个起点构成的二分图，边权是曼哈顿距离，要你求一个权值和最小的完美匹配。
这有什么意义嘛。没有。所以我比赛没写出来。
我们再思考一下：单论列的分配，我们可以发现，前 i 个目标，分配给前 i
个起点，肯定不会亏。也就是说，只有一行时，起点和目标点应该是按从左到右的顺序一一对应的。
此外，有一个非常重要且明显的结论：一个点如果要变行，最多只会变一次。
这里就产生了一种非常暴力的做法：枚举每个点是否要变行，先变完行再按上面的贪心策略求解。
我们再进一步观察一下，变行后，答案会发生什么变化。
假如你用一种变行方式求出来的解是 ，那么你换另一种变行方案，它肯定要一个上去一个下来（因为行的数量要对应）。
我们用 表示初始矩阵第一行的 m 个点，用 表示第二行的 n
个点。
同理用 和
表示目标矩阵的。并且记上下移动的次数为 。
此时有：
题解的贪心策略我压根就没看懂。所以我们来看看能不能 dp 吧。
我们可以用 f[i] 表示上面已经匹配了 i
个点，此时的最小步数。我们是从左往右扫的，这个玩意显然是没有后效性的。而且假如我们当前已经扫了
k 个点，那下面就匹配了 k - i 的点。可以得到一个转移方程（当前点为 ）：
或者说
但是这样是 的啊，直接 dp
是自然不行的。
算了，还是看看题解的做法是什么吧。
题解把
的答案做了更进一步的转换：我们记 表示初始矩阵第 i 行前 j
个位置共有多少个 1，
表示目标矩阵的对应值。
于是，我们有 。
用心去感受一下，这个式子是对的。
重要的是，这个式子把难以处理的点坐标差值变化转化成了很好处理的前缀和的区间变化。
例如，如果 的点被挪到了
，那它会使得 全部减少 1，而 全部加 1。
我们记 ，则有
当 的点被挪到了 ，它会使得 全部减少
1，而 全部加 1。
我们这个式子里面的
都是以绝对值出现的，而由移动引起的变化方向是相反的。并且，从定义上不难看出，随着
i 的移动，
值一次的变化不会超过 1。
所以，我们可以这样贪心：每当我们扫到一个位置，它的 和
异号时，我们进行交换（因为每次变化都最多是
1，所以此处一定有点可换），把点从正的那一行换到负的那一行（首先 s
加一，然后 i 后面的 delta 都要变）。
因为你的 s 只会加 1，而这两个数的绝对值分别少了
1，是赚的。这样至少在当前位置上看，它是赚的。
至于为什么这个策略在全局是对的，题解的证明太长了。我感性地理解一下：
首先你这两 delta 到最后肯定都是 0，因为数量会对上。
另外，这样换的话，你的 delta 绝对值是在减少的。我们知道 delta
每次变化最多是 1。
如果你这里减少了绝对值，那下一次变化也是不会亏的（减到 0，后面变成
1，如果你不减的话原本也是 1，这个 1 还可能多影响了几步，不亏；没减到
0，后面要么加回来要么变得更少，不可能比不减的代价多，不亏）。
总之不懂啊，好难。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n, A[2][N], B[2][N], d[2][N];
inline int sgn(int x) {
if(x == 0) return 0;
return x > 0 ? 1 : -1;
}
int main() {
scanf("%d", &n);
int cn = 0;
for(int i = 0; i < 2; i++) for(int j = 1; j <= n; j++) {
scanf("%d", A[i] + j), cn += A[i][j];
A[i][j] += A[i][j - 1];
}
for(int i = 0; i < 2; i++) for(int j = 1; j <= n; j++) {
scanf("%d", B[i] + j), cn -= B[i][j];
B[i][j] += B[i][j - 1];
}
if(cn != 0) {
puts("-1");
return 0;
}
int up = 0, down = 0; ll res = 0;
for(int i = 1; i <= n; i++) {
d[0][i] = A[0][i] - B[0][i] + up;
d[1][i] = A[1][i] - B[1][i] + down;
if(sgn(d[0][i]) * sgn(d[1][i]) == -1) {
if(d[0][i] > 0) up--, down++, d[0][i]--, d[1][i]++;
else up++, down--, d[0][i]++, d[1][i]--;
res++;
}
res += abs(d[0][i]) + abs(d[1][i]);
}
printf("%lld\n", res);
return 0;
}
|