これは本番すんなり思いつけた。
https://code.google.com/codejam/contest/3014486/dashboard#s=p1
問題
distinctな数値で構成されたN要素の数列A[i]が与えられる。
これらの数列の隣接要素のswapを繰り返し、A[0] < A[1] < A[2] < .. < A[m] > A[m-1] > ... > A[N-1]となるようにしたい。
最小で何回swapを行えばよいか。
解法
A[i]を小さい順に見て、Aの先頭または末尾の近い方に移動させれば良い。
以下のコードは先頭または末尾に移動した要素をその都度削除しており、O(N^2)で処理している。
void solve(int _loop) { int f,i,j,k,l,x,y; int N; vector<int> V; cin>>N; FOR(i,N) cin>>x, V.push_back(x); int ret=0; FOR(i,N) { x=0; FOR(j,V.size()) if(V[j]<V[x]) x=j; ret+=min(x,(int)V.size()-1-x); V.erase(V.begin()+x); } _P("Case #%d: %d\n",_loop,ret); }
解法
最大値をどこに置こうと考えると大変だけど、小さいものを一回外に出してしまえば後は考慮しなくてよい、と考えるとラク。