[原创]Codechef Matrix Transformation 【数学】

2017-06-28 20:14:52 Tabris_ 阅读数：282

博客爬取于2020-06-14 22:39:51
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/73863598

题目链接：https://www.codechef.com/problems/MTRNSFRM
———————————————————————————————————————————
Chef has two n × m matrices A and B. He wants to make them completely identical, to achieve this goal, he can perform the following actions in a single move:

Choose one of the matrices, either A or B.
Choose either one row or one column of the selected matrix.
Increment all the numbers in the selected row or column by 1.
Now Chef is wondering, what is the minimal number of moves he has to perform in order to make matrices A and B equal? Or is it just impossible?

Input
The first line of the input contains an integer T denoting the number of test cases.

For each test case, the first line of input contains two integers n and m.

The following n lines contain m space separated integers each ― the matrix A.

The next n lines contain m space separated integers each ― the matrix B.

Warning! The size of the input file can be up to 10 MB!

Output
For each test case, output a single integer ― the minimal number of moves Chef has to perform in order to make matrices A and B equal or -1 if this is not possible.
Constraints
1 ≤ T ≤ 100
1 ≤ n ≤ m ≤ 105
1 ≤ n × m ≤ 105
Let us denote the sum of n × m over all T testcases by S
1 ≤ S ≤ 5 · 105
1 ≤ Aij ≤ 109
1 ≤ Bij ≤ 109
Example
Input:
3
2 2
1 1
1 1
1 2
3 4
2 2
1 9
9 1
9 1
1 9
1 4
4 5 7 1
2 3 4 5

Output:
3
-1
9
Explanation
Example case 1. We can transform the matrix A into B in three moves:
1 1 -> 1 2 -> 1 2 -> 1 2
1 1 -> 1 2 -> 2 3 -> 3 4
Example case 2. It is impossible to make these matrices equal using only the allowed moves.
Example case 3. We can transform matrix A into 4 5 7 7 in six moves and matrix B into the same 4 5 7 7 in three moves.

————————————————————————————————————————————
题目大意:

这两个矩阵 每次操作可以选出一个矩阵在它的任意一行或/列上加1,问你最少多少次操作使两矩阵完全一样

第一点很好想

将两个矩阵合在一起,生成一个新矩阵, 那么题目就相当于这个新矩阵可以再一行/列上加/减11,最少多少次能变成全0矩阵.

这样会有两个操作x[i],y[i]x[i],y[i],分别代表第i行/列的操作次数

显然对于新矩阵有a[i][j]=x[i]+y[j];a[i][j]=x[i]+y[j];
多以不满足这个条件的就是-1了

然后想啊？ 怎么搞啊？ 看了看这个数据范围,差分约束？？！ ，好像很牵强啊， 我一个没写过查分约束的还是换个思路吧，

然后考虑，
a[i][j]=x[i]+y[j],a[i][j]=x[i]+y[j],
a[k][l]=x[k]+y[l];a[k][l]=x[k]+y[l];
那么同时有
a[i][l]=x[i]+y[l];a[i][l]=x[i]+y[l];
a[k][j]=x[k]+y[j];a[k][j]=x[k]+y[j];

易得a[i][j]+a[k][l]==a[i][l]+a[k][j];a[i][j]+a[k][l]==a[i][l]+a[k][j];

但是这样 我们要枚举两个点进行判断么？ no O(n^2)的复杂度是不能接受的

然后在想

我们能够发现
a[i][j]+a[k][l]==a[i][l]+a[k][j];a[i][j]+a[k][l]==a[i][l]+a[k][j];
a[i][j]+a[o][p]==a[i][p]+a[o][j];a[i][j]+a[o][p]==a[i][p]+a[o][j];
成立

那么一定有
a[o][p]+a[k][l]==a[o][l]+a[k][p];a[o][p]+a[k][l]==a[o][l]+a[k][p];

所我们只要固定a[k][l]枚举a[i][j]就好了，

接下里就是求解了

答案显然是∑x[i]+∑y[j]\sum x[i]+\sum y[j]

但是我们求的是最小解。

这时候我们设x[1]=tx[1]=t

易得此时答案是∑abs(a[i][1]−a[1][1]−t)+∑abs(−a[1][j]−t)\sum abs(a[i][1] - a[1][1] - t)+\sum abs( - a[1][j] - t)

当t为中间值时最小，证明略

Codechef为什么这个强势，这只是个EASY难度啊啊啊啊

附本题代码
————————————————————————————————————————————

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 1e5+7;
const int MOD = 1e9+7;

# define abs(x) ((x)>0?(x):-(x))

inline LL read(){
    LL x=0;char ch=getchar();
    for(;ch<'0'||'9'<ch;ch=getchar());
    for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
    return x;
}

/***************************************************************/

vector<int>a[N];

int main(){
    int _,m,n;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            a[i].push_back(0);
            for(int j=1,x;j<=m;j++){
                scanf("%d",&x);
                a[i].push_back(x);
            }
        }

        for(int i=1;i<=n;i++)
            for(int j=1,x;j<=m;j++){
                scanf("%d",&x);
                a[i][j]-=x;
            }

        bool flag=true;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[1][1]+a[i][j]==a[1][j]+a[i][1]) continue;
                flag=false;break;
            }
            if(!flag) break;
        }
        if(!flag) {
            puts("-1");
        }
        else {
            vector<int> pts;
            for(int i=1;i<=n;i++) pts.push_back(a[i][1]-a[1][1]);
            for(int j=1;j<=m;j++) pts.push_back(-a[1][j]);
            sort(pts.begin(), pts.end());
            int mid = (n+m)/2;

            LL ans = 0;
            for(int i=0; i<pts.size();i++)
                ans += abs(pts[mid]-pts[i]);

            printf("%lld\n", ans);
        }
        for(int i=1;i<=n;i++) a[i].clear();
    }
    return 0;
}