1090 In the army now

問題:

数の列が与えられる. その列は昇順に並んでいるものを期待する. もし, 前に大きな値が存在した場合は, その個数だけjumpするとする. 問題は, 列の長さが10000と大きいこと.

基本解法:

単純なソートを行うことでカウントすることができるのだけれども, O(n^2)のアルゴリズムではTime Limit Exceedになってしまう.

解法:

そこで, より高速なアルゴリズムを使って, カウントすれば良い.

プログラム

松崎: マージソートを使って計算を行った. file1090.matsuzaki.cpp


添付ファイル: file1090.matsuzaki.cpp 491件 [詳細]

Last-modified: 2009-11-06 (金) 13:25:51 (3364d)