哈尔滨理工大学2016新生赛C题

浏览: 248 发布日期: 2017-07-01 分类: c++

本文为您介绍哈尔滨理工大学2016新生赛C题的文章,具体方法请看介绍

一个r行c列的矩阵里的所有元素都为0或1,给出这个矩阵每一行的和以及每一列的和,那么是否存在这样一个矩阵满足条件呢,如果存在任意一个满足条件的矩阵则输出YES,如果不存在则输出NO?

每组测试数据第一行包含两个整数r,c,表示矩阵的行数和列数。

第二行包含r个32位无符号数,表示矩阵每行的和。

第三行包含c个32位无符号数,表示矩阵每列的和。

(1 <= r,c <= 100000)

如果存在这样的一个01矩阵,输出YES,否则输出NO

首先需要判断行和列的总和是否相等,因为它们都应该是整个矩阵的所有元素之和。如果他们不相等则这个矩阵肯定不存在。

这道题的贪心策略是,把列和从大到小枚举,对每个列和,按行和从大到小的顺序进行选择填上1,然后该行的行和减去1.这种贪心策略之所以有效,是因为这种策略会使各行的行和趋向于平均,尽可能地使行和减为零的情况推迟发生,而行和减为零意味着,当前可选的行数减少1,因此后面的计算可选择方法肯定比这种贪心的策略要少。

#include 
#include 
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

多多关注织梦者,我们将为您收集更多的C++相关文章.

返回顶部