2 ralphfjy RALPHFJY 于 2017.01.02 13:24 提问

这个的突破扣在哪,能给点启发吗
c

简易矩阵
时间限制:1000 ms | 内存限制:65535 KB

描述
这天,Yougth给冷淡一个m*n的矩阵,矩阵中的元素只有0和1,并且给出矩阵中每一行每一列的元素的和,问他是否存在这样一个矩阵。

这道题目可把冷淡难住了,你能帮他解决吗?

输入
输入包括多组测试数据,每个测试数据包括三行,首先第一行是两个数m和n,m是矩阵的行数,n是列数。然后第二行是m个数,表示矩阵每行的和,第三行n个数表示每列的和。(1<=m,n<=100000)
输出
如果存在这样的矩阵,输出YES,否则输出NO。
样例输入
1 1
0
1
1 1
1
1
样例输出
NO
YES

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.02 18:42
已采纳
 能想到的一个思路,首先根据横行的和构建矩阵,并且假设每行数据是1...1 0...0的形式。
然后根据列,调整每行,将多余的1和后面列的0交换,直到整个矩阵排出或者排不出,终止。
比如
3 3
1 2 3
2 1 3
这样的数据
首先排出
1 0 0
1 1 0
1 1 1
然后凑第一列,
0 1 0
1 1 0
1 1 1
使得第一列满足2
然后
0 0 1
1 0 1
1 1 1
最后3满足,结束,构造完成。
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!