Codeforces Round #557 B. Double Matrix

梦里梦外; 2021-09-29 22:18 153阅读 0赞

# 题面： #

[传送门 ][Link 1]

# 题目描述： #

给出两个n\*m的矩阵，问：是否能通过交换两个矩阵“对应”位置的元素，使两个矩阵都为“递增”矩阵。

“递增”矩阵定义：每行和每列都要“递增”。

# 题目分析： #

这道题就是个贪心水题，但是我刚开始就是胡思乱想，思路根本不对，再加上放假后的懒惰，就。。。进入正题：

我们可以想出这样一种贪心策略：让前面的值尽可能小，后面才有更大的机会成为“递增”矩阵。我们根据这个贪心策略，可以推出一些东西：

注：下面的a，b是两个题目给出的矩阵

假设我要让a(i, j)尽可能小，也就是：如果a(i, j) > b(i, j)，那么就交换a(i, j)和b(i, j)，否则不交换。

接下来我们看a(i+1, j)怎么处理？由贪心策略可知，a(i+1, j)和a(i, j)的处理方式一样。

所以，第一步，我们先使矩阵a的所有元素，小于等于矩阵b的所有元素。这时有：a(i, j) <= b(i, j)   (1 <= i <= n, 1 <= j <= m)

第二步，我们直接“贪心地选择”：检查a矩阵是否递增，如果不递增，就交换。如果交换后还不是严格递增就是“impossible”。

为什么？由于我们按照前面的贪心策略设置后，前面的值已经是在合法的情况下是最小的了，如果通过这次交换都不能符合严格递增，就是“impossible”。

检查完a矩阵后，直接看b矩阵是否合法。如果b矩阵不是每行每列严格递增，就是“impossible”，为什么？

当b矩阵有某行（列）的某个元素不是严格递增时，肯定要通过“交换”来符合某行（列）递增，但问题是：

假如b(i, j)在检查a矩阵时没交换过，也就是a(i, j) <= b(i, j)。大的（b(i, j)）都不能满足递增，交换后小的（a(i, j)）更不能满足递增了。

假如b(i, j)在检查a矩阵时交换过，也就是说，因为a矩阵不符合题意才交换的，这时如果再交换一次，虽然b矩阵可能符合题意，但是a矩阵又不符合题意了。

综上，只要b矩阵不合法，就输出"impossible"。

AC代码（ps：之前我想边交换边检查a矩阵，但是老是wa，所以最终写了个交换完后再检查的代码）：

1 #include <iostream>
     2 #include <cstdio>
     3 using namespace std;
     4 int n, m;
     5 int a[55][55], b[55][55];
     6  
     7 bool check(int a[][55], int mode){  //mode == 1: 对矩阵a进行操作, mode == 2: 检查是否合法
     8     for(int i = 0; i < n; i++){
     9         for(int j = 0; j < m; j++){
    10             if(i > 0 && a[i-1][j] >= a[i][j]){
    11                 if(mode) swap(a[i][j], b[i][j]);
    12                 else return false;
    13             }
    14             if(j > 0 && a[i][j-1] >= a[i][j]){
    15                 if(mode) swap(a[i][j], b[i][j]);
    16                 else return false;
    17             }
    18         }
    19     }
    20     return true;
    21 }
    22  
    23 void init(int a[][55]){
    24     for(int i = 0; i < n; i++){
    25         for(int j = 0; j < m; j++){
    26             scanf("%d", &a[i][j]);
    27         }
    28     }
    29 }
    30  
    31 int main(){
    32     scanf("%d%d", &n, &m);
    33     init(a); init(b);
    34  
    35     for(int i = 0; i < n; i++){
    36         for(int j = 0; j < m; j++){
    37             if(a[i][j] > b[i][j]){
    38                 swap(a[i][j], b[i][j]);  //第一步
    39             }
    40         }
    41     }
    42  
    43     //第二步
    44     check(a, 1);   //需要交换就交换
    45  
    46     if(!check(a, 0) || !check(b, 0)){   //检查矩阵a和矩阵b是否合法
    47         printf("Impossible\n");
    48         return 0;
    49     }
    50     printf("Possible\n");
    51     return 0;
    52 }

转载于:https://www.cnblogs.com/happy-MEdge/p/11159309.html

[Link 1]: http://codeforces.com/contest/1162/problem/B