AOJ : 2208 - トーマス・ライトの憂鬱 (The Melancholy of Thomas Right)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2208
日本語の問題文があるので省略

アルゴリズム

Greedyな感じで解けます.
サンプルを実際に手で書いてみるとわかりますが, 必ず大きい数の列から順番に答えを決定づけることができます.
そのため, 列側の数列を降順に並び替え, これを順番に見ていき, パズルが一通りに決定できるかを調べていけば, 解けます.
何言ってるかわからないので, ソースの方見てください.

プログラム

int n;
int t[10001],s[10001];

int main(void){
  while(cin>>n,n){
    for(int i=0;i<n;i++) cin>>t[i];
    for(int i=0;i<n;i++) cin>>s[i];
    sort(s,s+n);
    reverse(s,s+n);

    bool flg = true;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(t[j] > 0){ //この行の中にONにできるものが残っているなら
          t[j]--;
          s[i]--;
        }
      }

      if(s[i] != 0){ //ちょうど使い切れなかったらダメ
        flg = false;
        break;
      }
    }

    cout<<(flg ? "Yes" : "No")<<endl;
  }

  return 0;
}