简易矩阵
时间限制: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...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满足,结束,构造完成。