SRM306 div2

headにもtailにも移動できる時．

a:      8  12  25  7  15  19

sorted :7  8  12  15  19  25
動かす回数を少なくしたいわけだから、どうしても動かさなければならない数字をカウントする．
たとえば、aの部分列[12  15  19]は既にソートされているので、8, 12, 7を動かさなければならない．
ということは三回動かす必要がある．

しかしながら、8が一番端にきているのでもっと最適化できて、
例えば、aの部分列[8 12 15 19]に着目すると、二回動かすだけで済む．これが解となる．
該当する部分列の長さが最大になるようにすれば
sz-(最大の長さ)
で答えが出る．

これをなんとかして実装する．

    vector sorted = a;
    sort(sorted.begin(), sorted.end());
    int sz = sorted.size();
    int ans = sz;
    for(int i = 0; i < sz; i++) {
      int at = i; int cnt = 0;
      for(int j = 0; j < sz; j++) {
	if(at < sz) {
	  if(sorted[at] == a[j]) at++;
	  else cnt++;  //該当する部分列に属さない数字の数をひとつづつカウントする．
	}
      }
      ans = min(ans, cnt);
    }
    return ans;
  }

tailだけにしか移動できない時．

1  3  4  5  6  7  8  9  2

1  2  3  4  5  6  7  8  9
該当する部分列は[1,2]なので、残りを末尾に移動しなければならない．

  int countMoves(vector  a) {
    int sz = a.size();
    vector sorted = a;
    sort(sorted.begin(), sorted.end());
    int at = 0; int fix = 0;
//ループを一回減らしている．
    for(int i = 0; i < sz; i++) {
      if(sorted[at] == a[i]) {
	at++; fix++;
      }
    }
    return sz-fix;
      
  }