首页 > 代码库 > 【贪心】 Codeforces Round #419 (Div. 1) A. Karen and Game

【贪心】 Codeforces Round #419 (Div. 1) A. Karen and Game

容易发现,删除的顺序不影响答案。

所以可以随便删。

如果行数大于列数,就先删列;否则先删行。

#include<cstdio>
#include<algorithm>
using namespace std;
int p1,ans1[510*110],ans2[510*110],p2;
int n,m,a[110][110];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	if(n<=m){
		for(int i=1;i<=n;++i){
			int minn=*min_element(a[i]+1,a[i]+m+1);
			for(int j=1;j<=minn;++j){
				ans1[++p1]=i;
			}
			for(int j=1;j<=m;++j){
				a[i][j]-=minn;
			}
		}
		for(int i=1;i<=m;++i){
			int minn=2147483647;
			for(int j=1;j<=n;++j){
				minn=min(minn,a[j][i]);
			}
			for(int j=1;j<=minn;++j){
				ans2[++p2]=i;
			}
			for(int j=1;j<=n;++j){
				a[j][i]-=minn;
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(a[i][j]>0){
					puts("-1");
					return 0;
				}
			}
		}
		printf("%d\n",p1+p2);
		for(int i=1;i<=p1;++i){
			printf("row %d\n",ans1[i]);
		}
		for(int i=1;i<=p2;++i){
			printf("col %d\n",ans2[i]);
		}
	}
	else{
		for(int i=1;i<=m;++i){
			int minn=2147483647;
			for(int j=1;j<=n;++j){
				minn=min(minn,a[j][i]);
			}
			for(int j=1;j<=minn;++j){
				ans2[++p2]=i;
			}
			for(int j=1;j<=n;++j){
				a[j][i]-=minn;
			}
		}
		for(int i=1;i<=n;++i){
			int minn=*min_element(a[i]+1,a[i]+m+1);
			for(int j=1;j<=minn;++j){
				ans1[++p1]=i;
			}
			for(int j=1;j<=m;++j){
				a[i][j]-=minn;
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(a[i][j]>0){
					puts("-1");
					return 0;
				}
			}
		}
		printf("%d\n",p1+p2);
		for(int i=1;i<=p2;++i){
			printf("col %d\n",ans2[i]);
		}
		for(int i=1;i<=p1;++i){
			printf("row %d\n",ans1[i]);
		}
	}
	
	return 0;
}

【贪心】 Codeforces Round #419 (Div. 1) A. Karen and Game