结论1：矩阵$B$能被得到当且仅当满足以下条件——

1.$\forall i\ge 2,\sum_{j=1}^{W}(-1)^{i+j}A_{i,j}=\sum_{j=1}^{W}(-1)^{i+j}B_{i,j}$

2.$\forall j\ge 2,\sum_{i=1}^{H}(-1)^{i+j}A_{i,j}=\sum_{i=1}^{H}(-1)^{i+j}B_{i,j}$

必要性：每一次操作均不会改变上述值，因此显然成立

充分性：按顺序依次操作使得$A_{i,j}=B_{i,j}$，最终剩下的值由必要性被唯一确定，必然相同

将$A_{i,j}$和$B_{i,j}$均乘上$(-1)^{i+j}$，条件也即每行每列元素和相同

记$x_{i}$为$A$和$B$第$i$行的元素和的差，$y_{j}$为$A$和$B$第$j$列的元素和的差（初始$B_{i,j}$均为0）

考虑调整，将$B_{i,j}$增加$t$即使得$x_{i}$和$y_{j}$分别减小$t$并花费$|t|$的代价，最终要求$x_{i}$和$y_{j}$均为0

结论2：上述问题的最小代价为$\max(\sum_{i=1}^{H}|x_{i}|,\sum_{j=1}^{W}|y_{j}|)$

每花费$t$的代价最多使得上述两值分别减小$t$，而最多为0，因此最小代价为该值

另一方面，考虑不断执行以下操作：

1.若存在$x_{i}y_{j}>0$，选择此类$(i,j)$并将$B_{i,j}$增加$sign(x_{i})$（符号函数）

2.若存在$x_{i}x_{j}<0$，不妨假设$x_{i}>0$，将$B_{i,1}$增加1$,B_{j,1}$减小1

注意到$\sum_{i=1}^{H}x_{i}=\sum_{j=1}^{W}y_{j}$，因此均不存在当且仅当$x_{i}$和$y_{j}$均为0

同时，若花费$t$的代价，总会使得$\max(\sum_{i=1}^{H}|x_{i}|,\sum_{j=1}^{W}|y_{j}|)$减小$t$

综上，即得证

关于如何取到最小值，参考证明中的构造即可（每一轮至少会使得一个数变为0）

时间复杂度为$o(n^{2})$，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 505
 4 #define ll long long
 5 vector<int>v1,v2;
 6 int n,m;
 7 ll ans,x[N],y[N],a[N][N];
 8 void upd(int i,int j,ll s){
 9     a[i][j]+=s,x[i]-=s,y[j]-=s;
10 }
11 int main(){
12     scanf("%d%d",&n,&m);
13     for(int i=1;i<=n;i++)
14         for(int j=1;j<=m;j++){
15             scanf("%lld",&a[i][j]);
16             if ((i+j)&1)a[i][j]=-a[i][j];
17             x[i]+=a[i][j],y[j]+=a[i][j];
18         }
19     memset(a,0,sizeof(a));
20     while (1){
21         int posi1=0,posi2=0,posj1=0,posj2=0;
22         for(int i=1;i<=n;i++){
23             if (x[i]>0)posi1=i;
24             if (x[i]<0)posi2=i;
25         }
26         for(int j=1;j<=m;j++){
27             if (y[j]>0)posj1=j;
28             if (y[j]<0)posj2=j;
29         }
30         if ((posi1)&&(posj1)){
31             upd(posi1,posj1,min(x[posi1],y[posj1]));
32             continue;
33         }
34         if ((posi2)&&(posj2)){
35             upd(posi2,posj2,max(x[posi2],y[posj2]));
36             continue;
37         }
38         if ((posi1)&&(posi2)){
39             ll s=min(x[posi1],-x[posi2]);
40             upd(posi1,1,s),upd(posi2,1,-s);
41             continue;
42         }
43         if ((posj1)&&(posj2)){
44             ll s=min(y[posj1],-y[posj2]);
45             upd(1,posj1,s),upd(1,posj2,-s);
46             continue;
47         }
48         break;
49     }
50     for(int i=1;i<=n;i++)
51         for(int j=1;j<=m;j++){
52             if ((i+j)&1)a[i][j]=-a[i][j];
53             ans+=abs(a[i][j]);
54         }
55     printf("%lld\n",ans);
56     for(int i=1;i<=n;i++){
57         for(int j=1;j<=m;j++)printf("%lld ",a[i][j]);
58         printf("\n");
59     }
60     return 0;
61 } 

View Code