题解：CF815A Karen and Game

· · 题解

本人的第二篇题解，请指教！

题面大意

给定一个大小为 n\times m 的二维数组，初始都为 0，每次可以使一行或一列的元素全部加 1，问最少需要多少次操作，才能使这个数组变成目标数组。

解法

可以用“正难则反”和贪心的思路，从目标数组开始，每次使一行或一列的元素全部减 1，最少需要多少次操作，才能使这个数组的每个元素都为 0。\ 每次可以按照行和列进行操作，减去一行或一列的最小值，然后记录答案。最后判断目标数组是否全为 0，如果有非零元素，输出 -1，否则输出最终答案。

注意：

如果 n>m，需要先按列进行操作，再按行进行操作。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1001][1001],ans[100001],c;
string ans2[100001];//ans：记录第几行/第几列 ans2：记录row/col c:操作次数 
void row(){
    for(int i=1;i<=n;i++){
        int mi=1e9;//mi:每一行的最小值 
        for(int j=1;j<=m;j++)mi=min(mi,a[i][j]);//查找一行的最小值
        for(int j=1;j<=m;j++)a[i][j]-=mi;//减少最小值（执行mi次减1） 
        if(mi)while(mi--)ans[++c]=i,ans2[c]="row ";//记录答案 
    }
}
void col(){//同上，按列进行操作 
    for(int i=1;i<=m;i++){
        int mi=1e9;
        for(int j=1;j<=n;j++)mi=min(mi,a[j][i]);
        for(int j=1;j<=n;j++)a[j][i]-=mi;
        if(mi)while(mi--)ans[++c]=i,ans2[c]="col ";
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];//输入数组 
    if(n>m)col(),row();//先按列进行操作，再按行进行操作
    else row(),col();//先按行进行操作，再按列进行操作
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]){//是否有非零元素 
                cout<<-1;//无解 
                return 0;
            }
        }
    }
    cout<<c<<"\n";//输出答案 
    for(int i=1;i<=c;i++)cout<<ans2[i]<<ans[i]<<"\n";
    return 0;
}

::: AC记录