Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2084-f10558a3
この記事にトラックバックする(FC2ブログユーザー)

UVa 12049 - Just Prune The List (この記事を編集する[管理者用])

Source

Next generation Contest 6 (2011-06-25)
UVa 12049

問題概要

2つの整数のリストが与えられる.各リストに含まれる整数の数は10000個以下.
整数を幾つか取り除いて,2つのリストに含まれる整数を一致させたい.(順番は一致していなくて構わず,同じ整数が同じ個数含まれているようにしたい)
最小で何個の整数を取り除けばよいかを求める問題.

解法

ある整数について,たくさん含んでいる方から,少ない方と含んでいる数が一致するまで減らせば良い.
それぞれのリストを昇順ソートして,最初から見て行って,同じ要素なら両方残して次を見る,違う要素なら小さい方を削除する,を繰り返していく.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2084-f10558a3
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。