Div1 Mediumが解けたのにこっちは1ミスした。
https://community.topcoder.com/stat?c=problem_statement&pm=14083
問題
N要素の異なる整数からなる数列が与えられる。
1回の処理で連続した(N-1)個の整数を任意に並べ替えられるとき、全体を昇順に並べるのにかかる最小処理回数を求めよ。
解法
まず最小値と最大値の位置だけ求めておく。
あとは丁寧に場合分けしよう。
- 最小値が先頭にある場合、残りは(N-1)要素なので1回処理すれば並べ替えられる。
- よって、全体が最初から昇順なら0回、そうでなければ1回
- 最小値が先頭でも末尾でもない場合、まず1回並べ替えて最小値を先頭に持ってくる。最大値が末尾にあれば、その1回で先頭(N-1)要素を昇順にして終わり。そうでなければもう1回処理する。
- 最小値が末尾にある場合、それを先頭に持ってくるのに最低2回かかる。また最大値が先頭にある場合、最初の2回でこの最大値を末尾に持って行けないのでもう1回処理する。
class BearSlowlySorts { public: int minMoves(vector <int> w) { int N=w.size(); int ma=0,mi=0,i; FOR(i,N) { if(w[ma]<w[i]) ma=i; if(w[mi]>w[i]) mi=i; } if(mi==0) { for(i=1;i<N-1;i++) if(w[i]>w[i+1]) return 1; return 0; } else if(mi<N-1) return 1+(ma!=N-1); else return 2+(ma==0); } }
まとめ
丁寧に場合分けしないと見落とす。
案の定正答率はちょっと低目。