いまいちふるわないなぁ。
https://codeforces.com/contest/2129/problem/B
問題
1~NのPermutation Pが与えられる。
N要素の整数列Aを、以下のように作る。
- A[i]はP[i]か2N-P[i]のいずれか
Aの転倒数の最小値を求めよ。
解法
P[i]<P[j]の時、A[j]がP[j]か2N-P[j]のどちらかであるというのはA[i]に影響しない。
A[i]をP[i]と2N-P[i]のどちらにするかだけで定まる。
そこでP[i]の大きい順に定めて行くとよい。
A[i]をP[i]と2N-P[i]のどちらか転送数の少ない方に合わせて取る。
int T,N; int P[5050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; FOR(i,N) cin>>P[i]; ll ret=0; for(i=1;i<=N;i++) { FOR(j,N) if(P[j]==i) k=j; x=y=0; FOR(j,N) if(P[j]!=-1&&j!=k) { if(j<k) { x++; } else { y++; } } ret+=min(x,y); P[k]=-1; } cout<<ret<<endl; } }
まとめ
これO(NlogN)で行ける気がするけど、なんでO(N^2)を許容するような入力なんだろ。