#419 Div2 Problem C Karen and Game (贪心 && 暴力)

题目链接：http://codeforces.com/contest/816/problem/C

题意 ：给出一个 n*m 的变化后的矩阵，变化前矩阵的元素全是0，变化的规则是选择其中的一行或者一列将元素进行加一操作，问你最少用几步操作能将全零的矩阵变成一开始输入的矩阵，如果无法做到则输出-1，否则输出操作的总次数以及具体的操作步骤。

分析 ：如果跟着题意顺着想如何从全零矩阵进行变化那可能比较费劲，不如将一开始输入的矩阵进行减的操作（即逆操作）使其最后变成全零矩阵可能会更简单操作，因为只是在原始矩阵进行变化。那如何减呢？可以注意到如果我们先枚举行的话，比如第1行，试想一下第一行最多能够进行多少次减的操作？不难想到这一行中最小的数便是可以进行的操作数，那我们只要枚举所有的行和列找出每一行的最小值，如果最小值>0则进行模拟操作并且记录方便最后的输出。但是这里有个坑，就是题目要求的是最小的操作总数，那对于一个所有元素都相同但是行数和列数都不相同的矩阵便有区别了，例如矩阵的元素都是1，但是n>m，如果此时先枚举1~n那便不是最优了，所以要注意枚举行和列的先后顺序，取决于n和m的相对大小。还有一个就是题目有无法实现就输出-1的情况，这里我们只要在一开始输入矩阵的时候记录所有元素的和，然后在减的时候我们不难得出减的总合，如果减的总和!=原矩阵元素总和，则说明无法实现。

 

#include<bits/stdc++.h>
using namespace std;
const int maxn = 101;
int G[maxn][maxn];
int n, m;
int row[maxn];
int col[maxn];
int row_cnt = 0;
int col_cnt = 0;
inline void col_work()
{
    for(int i=0; i<m; i++){
        int Min = 0x3f3f3f3f;
        for(int j=0; j<n; j++){
            if(G[j][i] < Min)
                Min = G[j][i];
        }
        if(Min>0){
            col_cnt++;
            col[i]++;
            for(int j=0; j<n; j++){
                G[j][i]--;
            }
            i--;//因为减一次可能还不够，所以再判断一次这列是否可以再减
        }
    }
}
inline void row_work()
{
    for(int i=0; i<n; i++){
        int Min = 0x3f3f3f3f;
        for(int j=0; j<m; j++){
            if(G[i][j] < Min)
                Min = G[i][j];
        }
        if(Min>0){
            row_cnt++;
            row[i]++;
            for(int j=0; j<m; j++){
                G[i][j]--;
            }
            i--;
        }
    }
}
int main(void)
{
    int sum = 0;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &G[i][j]);
            sum += G[i][j];
        }
    }
    if(n > m){
        col_work();
        row_work();
    }else{
        row_work();
        col_work();
    }
    if((row_cnt * m + col_cnt * n)!=sum){//无法实现的情况
        puts("-1");
        return 0;
    }
    printf("%d
", row_cnt+col_cnt);
    for(int i=0; i<n; i++){
        while(row[i]--)//这里用一个row数组来记录这一行进行了多少次减操作，col数组也是同样道理
            printf("row %d
", i+1);
    }
    for(int i=0; i<m; i++){
        while(col[i]--)
            printf("col %d
", i+1);
    }
    return 0;
}