1090 In the army now †

問題: †

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

基本解法: †

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

解法: †

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

プログラム †

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