哈尔滨理工大学2016新生赛C题
2018-06-17 23:33:55来源:未知 阅读 ()
一个r行c列的矩阵里的所有元素都为0或1,给出这个矩阵每一行的和以及每一列的和,那么是否存在这样一个矩阵满足条件呢,如果存在任意一个满足条件的矩阵则输出YES,如果不存在则输出NO?
每组测试数据第一行包含两个整数r,c,表示矩阵的行数和列数。
第二行包含r个32位无符号数,表示矩阵每行的和。
第三行包含c个32位无符号数,表示矩阵每列的和。
(1 <= r,c <= 100000)
如果存在这样的一个01矩阵,输出YES,否则输出NO
首先需要判断行和列的总和是否相等,因为它们都应该是整个矩阵的所有元素之和。如果他们不相等则这个矩阵肯定不存在。
这道题的贪心策略是,把列和从大到小枚举,对每个列和,按行和从大到小的顺序进行选择填上1,然后该行的行和减去1.这种贪心策略之所以有效,是因为这种策略会使各行的行和趋向于平均,尽可能地使行和减为零的情况推迟发生,而行和减为零意味着,当前可选的行数减少1,因此后面的计算可选择方法肯定比这种贪心的策略要少。
#include <stdio.h> #include <algorithm> using namespace std; const int size=100000; //最大行列数 int a[size],b[size]; //分别保存行和与列和 int main(){ int r,c,i,j; long long s,t; //枚举时比较的行和与列和总数 while(scanf("%d%d",&r,&c)==2){//输入整数r,c直到文件结束 for(i=0,s=0; i<r; i++){ scanf("%d",&a[i]); //输入行和 s+=a[i]; //累加行和 } for(i=0,t=0; i<c; i++){ scanf("%d",&b[i]); //输入列和 t+=b[i]; //累加列和 } if(s!=t){ //如果行和与列和总数不相等 printf("NO\n"); //则不可能有解 continue; } sort(a,a+r); //行和排序 sort(b,b+c); //列和排序 for(i=j=0,t=s=0; i<c; i++){//从大到小枚举列和 t+=b[c-i-1]; //当前已枚举的列和总数 s+=r-j; //当前可用的行和总数 while(j<r&&a[j]<i+1){ //如果某行和小于枚举列数 s-=i+1-a[j]; //把行和总数多算出来的部分减去 j++; } if(s<t) break; //如果可用行和小于当前列和则不可能有解 } printf(i==c?"YES\n":"NO\n");//输出答案 } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:How To Use Goto?
- 2020年3月28日UCF Local Programming Contest 2016 2020-03-31
- 洛谷P4071-[SDOI2016]排列计数 题解 2020-01-12
- 哈尔滨网络热身赛 2019-11-25
- [NOIP2016]天天爱跑步-题解 2019-10-08
- CSP201612-2:工资计算 2018-09-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash