cf #419(div2) C.Karen and Game(贪心)

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

题目大意:给定一个n*m的矩阵,每次操作可以使其中一行或一列减1,求使得矩阵变为0的最少操作数及一个可行方案.

分析:注意到有解的充要条件是所有行的和mod n 余数相同,所有列的和mod m 余数相同,而每次操作不改变这一性质,故可以贪心,不妨设n<m,则先对行操作,使得每行都出现0,再对列操作,就可以得到一个可行解.

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn=105;
 6 int n,m,g[maxn][maxn],opr[maxn],opc[maxn];
 7 int main(){
 8     int sum=0;
 9     bool Swap=false;
10     memset(opr,0,sizeof(opr));
11     memset(opc,0,sizeof(opc));
12     cin>>n>>m;
13     if(n>m){
14         for(int i=0;i<n;i++)
15             for(int j=0;j<m;j++)
16                 cin>>g[j][i];
17         int k=n;n=m;m=k;
18         Swap=true;
19     }else{
20         for(int i=0;i<n;i++)
21             for(int j=0;j<m;j++)
22                 cin>>g[i][j];
23     }
24     for(int i=0;i<n;i++){
25         int MIN=505;
26         for(int j=0;j<m;j++)
27             MIN=min(MIN,g[i][j]);
28         for(int j=0;j<m;j++)
29             g[i][j]-=MIN;
30         opr[i]=MIN;
31         sum+=MIN;
32     }
33     for(int j=0;j<m;j++){
34         int MIN=505;
35         for(int i=0;i<n;i++)
36             MIN=min(MIN,g[i][j]);
37         for(int i=0;i<n;i++)
38             g[i][j]-=MIN;
39         opc[j]=MIN;
40         sum+=MIN;
41     }
42     for(int i=0;i<n;i++)
43         for(int j=0;j<m;j++){
44             if(g[i][j]){
45                 cout<<-1<<endl;
46                 return 0;
47             }
48         }
49     char s[10];
50     cout<<sum<<endl;
51     for(int i=0;i<n;i++){
52         if(opr[i]){
53             if(!Swap)sprintf(s,"row %d",i+1);
54             else sprintf(s,"col %d",i+1);
55             while(opr[i]--)
56                 cout<<s<<endl;
57         }
58     }
59     for(int i=0;i<m;i++){
60         if(opc[i]){
61             if(!Swap)sprintf(s,"col %d",i+1);
62             else sprintf(s,"row %d",i+1);
63             while(opc[i]--)
64                 cout<<s<<endl;
65         }
66     }
67     return 0;
68 }