首页 > 代码库 > 【贪心】 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。