哈爾濱理工大學2016新生賽C題，哈爾濱理工大學2016

哈爾濱理工大學2016新生賽C題，哈爾濱理工大學2016

一個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;
}