When Can We Meet? 解説
- 問題名:When Can We Meet? (PKU)
- 出典:Problem A, ACM/ICPC Japan Domestic, 2003-10-03
- 難易度:☆
- 問題の種類:探索
- 解法:同一要素数のカウント(int型配列)
- 解答ソースコード:
アルゴリズムの概略
1~99日後の中で最も集まれる人数が多い日を出力すればよいので, int date[100] という配列を宣言して(全て値 0 で初期化する), 空いている日 d をそれぞれ date[d]++ としてカウントアップしていけばOKです。 これで「X日後にはY人が空いている」ということが分かります。 後はその中で最大値を求めれば,それが解となります。
アルゴリズムの計算量
入力数 n × m に対して,カウントアップはそれぞれ定数なのでカウント部分の計算量は O(n×m) になります。 最大値を求める部分は,何日後を表す入力の最大値 a とすると O(a) になります。 カウント部分の O(n×m) はそもそも入力を読む計算量と同じで問題とならず, O(a) は 0 < a < 100 なので全く問題となりません。
アルゴリズムの実装
データを読み込んでカウントするだけなので実装は非常に簡単です。 問題文にあるように,同じ最大値が複数あれば最初のものを出力するようにプログラムを書きます。 また,Quotaのところを読み落とさないようにしましょう(max < Q ならば 0 を出力)。
$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $