首页 > 代码库 > #419（div2) C. Karen and Game

#419（div2) C. Karen and Game

2024-10-08 01:35:02   217人阅读

题意：给出一个n*m的矩阵，然后我们可以每一行-1，每一列-1，问是否可以全部变成0

思路：最开始的时候马上就想到了无论怎样，他每一行该减去的时候无论先后都要减去，那么我每一行取一个最小值减去，然后每一列取最小值减去，然后判断是否全部为0，然后学弟给了我一组数据，3 2 2 2 1 1 2 2，题要求最少步骤，那么我们那样就不可以，所以得判断下n和m的大小，n大先做列，那样就减去的数字更多了，m大反之亦然。（手速狗靠这涨了一波大分，o(*￣▽￣*)ブ）

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 int a[105][105];
  5 int hang[105],lie[105];
  6 int n,m;
  7 struct node{
  8     int x,y;
  9 }e[200002];
 10 
 11 int main(){
 12     memset(hang,127,sizeof(hang));
 13     memset(lie,127,sizeof(lie));
 14     scanf("%d%d",&n,&m);
 15     int l=0;
 16     for(int i=1;i<=n;i++)
 17         for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
 18     if(n<=m){
 19 
 20         for(int i=1;i<=n;i++){
 21         for(int j=1;j<=m;j++){
 22         hang[i]=min(hang[i],a[i][j]);
 23         }
 24     }
 25     for(int i=1;i<=n;i++){
 26          if(hang[i]>0){
 27             for(int j=1;j<=m;j++)
 28             {
 29                 a[i][j]-=hang[i];
 30 
 31             }
 32             while(hang[i]--){
 33                 e[l].x=1;e[l++].y=i;
 34             }
 35 
 36          }
 37     }
 38     for(int i=1;i<=m;i++){
 39         for(int j=1;j<=n;j++){
 40             lie[i]=min(lie[i],a[j][i]);
 41         }
 42     }
 43     for(int i=1;i<=m;i++){
 44         if(lie[i]>0){
 45             for(int j=1;j<=n;j++)
 46             {
 47                 a[j][i]-=lie[i];
 48 
 49             }
 50             while(lie[i]--){
 51                 e[l].x=2;e[l++].y=i;
 52             }
 53 
 54         }
 55     }
 56     int sum=0;
 57     for(int i=1;i<=n;i++)
 58         for(int j=1;j<=m;j++)
 59         if(a[i][j]==0) sum++;
 60     if(sum!=n*m){
 61         printf("-1\n");
 62     }
 63     else {
 64             printf("%d\n",l);
 65         for(int i=0;i<l;i++){
 66             if(e[i].x==1) printf("row ");
 67             else printf("col ");
 68             printf("%d\n",e[i].y);
 69         }
 70       }
 71     }
 72     else {
 73 
 74             for(int i=1;i<=m;i++){
 75         for(int j=1;j<=n;j++){
 76             lie[i]=min(lie[i],a[j][i]);
 77         }
 78     }
 79     for(int i=1;i<=m;i++){
 80         if(lie[i]>0){
 81             for(int j=1;j<=n;j++)
 82             {
 83                 a[j][i]-=lie[i];
 84 
 85             }
 86             while(lie[i]--){
 87                 e[l].x=2;e[l++].y=i;
 88             }
 89 
 90         }
 91     }
 92          for(int i=1;i<=n;i++){
 93         for(int j=1;j<=m;j++){
 94         hang[i]=min(hang[i],a[i][j]);
 95         }
 96      }
 97     for(int i=1;i<=n;i++){
 98          if(hang[i]>0){
 99             for(int j=1;j<=m;j++)
100             {
101                 a[i][j]-=hang[i];
102 
103             }
104             while(hang[i]--){
105                 e[l].x=1;e[l++].y=i;
106             }
107 
108          }
109     }
110 
111     int sum=0;
112     for(int i=1;i<=n;i++)
113         for(int j=1;j<=m;j++)
114         if(a[i][j]==0) sum++;
115     if(sum!=n*m){
116         printf("-1\n");
117     }
118     else {
119             printf("%d\n",l);
120         for(int i=0;i<l;i++){
121             if(e[i].x==1) printf("row ");
122             else printf("col ");
123             printf("%d\n",e[i].y);
124         }
125       }
126     }
127 }

 

#419（div2) C. Karen and Game


联系
我们