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