割とすんなり思いつけた。
https://csacademy.com/contest/round-50/task/min-swaps/
問題
偶数Nに対し、1~Nのpermutationである数列Aが与えられる。
Aに対し、任意の2要素のSwapを繰り返し、隣接要素の差の絶対値の総和を最大にしたい。
最小何回のSwapで達成できるか。
解法
サンプルが親切。
条件を満たす数列は以下のいずれかである。
- 先頭がN/2で、以後偶数番目にN/2より大きく、奇数番目にN/2より小さい値が来る。最後は(N/2)+1。
- 先頭が(N/2)+1で、以後奇数番目にN/2より大きく、偶数番目にN/2より小さい値が来る。最後はN/2。
よって両方の候補に対し、それを満たすような最小swap回数を求めればよい。
int T; int N; int P[101010]; int Q[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; int L,R; FOR(i,N) cin>>P[i]; int mi=1<<30; FOR(i,2) { FOR(x,N) { if(i==0) Q[x]=P[x]; else Q[x]=P[N-1-x]; if(Q[x]==N/2) L=x; if(Q[x]==N/2+1) R=x; } int cost=0; if(L!=0) { cost++; swap(Q[0],Q[L]); if(R==0) swap(L,R); else L=0; } if(R!=N-1) { cost++; swap(Q[R],Q[N-1]); } for(x=1;x<N-1;x+=2) if(Q[x]<=N/2) cost++; mi=min(mi,cost); } cout<<mi<<endl; } }
まとめ
サンプルがこんな丁寧じゃなければ解ける人減ってそう。