これ系いつもLISが頭に思い浮かんで失敗するんだよね。
https://codeforces.com/contest/1240/problem/B
問題
整数列Aが与えられる。
この数列に対し以下の処理を繰り返し行い、Aを昇順にソートしたい。
- ある整数を選び、その値を持つ要素をすべてまとめて数列の先頭か末尾に移動する
最小で処理回数が何回か。
解法
まず値を座標圧縮しておく。
最長で連続して昇順に並んでいる箇所を残すことを考えよう。
そうするとそのような項目を数え上げることになる。
座標圧縮後、ある値の初出の位置より、1小さい値の最後の登場位置が左にあるなら、その2値は処理を行わなくても連続にすることができる。
int Q; int N; int A[303030]; int L[303030]; int R[303030]; int C[303030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>Q; while(Q--) { cin>>N; vector<int> V; FOR(i,N) { cin>>A[i]; V.push_back(A[i]); } sort(ALL(V)); V.erase(unique(ALL(V)),V.end()); FOR(i,V.size()) { R[i]=C[i]=0; L[i]=1<<30; } FOR(i,N) { A[i]=lower_bound(ALL(V),A[i])-V.begin(); R[A[i]]=i; L[A[i]]=min(L[A[i]],i); } int ma=0; FOR(i,N) if(L[A[i]]==i) { if(A[i]==0) C[A[i]]=0; else { if(R[A[i]-1]<i) C[A[i]]=C[A[i]-1]+1; else C[A[i]]=0; } ma=max(ma,C[A[i]]); } cout<<V.size()-(ma+1)<<endl; } }
まとめ
前も似たような問題でLISに走って1ミスしたような。