【贪心，思维】CF1700F Puzzle
ZillionX
·
·
题解
Description
给出两个 2 \times n 的 01 矩阵 A,B，每次操作可以交换 A 中任意两个相邻位置的值，求使得 A = B 的最小操作次数。
# Solution
我们首先考虑 $1 \times n$ 矩阵的情况。
观察样例，不难发现结论：此时使得 $1 \times n$ 矩阵 $A=B$ 的最小操作次数即为
$$\sum_{i=1}^n |{\rm sum}A_i-{\rm sum}B_i|$$
其中 ${\rm sum}A_i= \sum\limits_{j=1}^i A_j$，${\rm sum}B_i$ 同理，对于上式的证明留作读者练习。
接下来考虑拓展到 $2 \times n$ 矩阵的情况，可以发现，无非就是对于原来单独的两行，增加了一个上下交换操作。
我们以将第一行的 $1$ 转移下去的上下交换操作为例，注意到，这会使第一行 $A-B$ 的前缀和减 $1$，而第二行则会加 $1$。
由于答案取绝对值，不难想到，若两行 $A-B$ 的前缀和同号，那么交换操作一定是没有意义的，不会使答案变优。
但是，若它们异号，我们则可以移动 $\min\{|{\rm sum}A_{i,1}-{\rm sum}B_{i,1}|,|{\rm sum}A_{i,2}-{\rm sum}B_{i,2}\}|$ 个 $1$，使得其中之一变为 $0$。这样可以将原来 $2$ 次的左右交换操作，优化为 $1$ 次的上下交换操作。
值得一提的是，尽管这样的移动具有后效性，但可以分析出来，它并不会使我们的答案变劣，因此这是合法的贪心做法。
至此我们就在 $\mathcal O(n)$ 的时间复杂度下完成了本题。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int n,a[2][N],b[2][N];
LL sum,Ans;
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[0][i]),sum+=a[0][i];
for (int i=1;i<=n;i++) scanf("%d",&a[1][i]),sum+=a[1][i];
for (int i=1;i<=n;i++) scanf("%d",&b[0][i]),sum-=b[0][i];
for (int i=1;i<=n;i++) scanf("%d",&b[1][i]),sum-=b[1][i];
if (sum) {
printf("-1");
return 0;
}
LL s0=0,s1=0;
for (int i=1;i<=n;i++) {
s0+=a[0][i]-b[0][i],s1+=a[1][i]-b[1][i];
if (s0<0 && s1>0) {
int nm=min(-s0,s1);Ans+=nm;s0+=nm,s1-=nm;
}
else if (s0>0 && s1<0) {
int nm=min(s0,-s1);Ans+=nm;s0-=nm,s1+=nm;
}
Ans+=abs(s0)+abs(s1);
}
printf("%lld",Ans);
return 0;
}
```