Codeforces #884 : F2. Min Cost Permutation (Hard Version)

部分点までは取れたけども。
https://codeforces.com/contest/1844/problem/F2

問題

整数列Aと整数Cが与えられる。
AのPermutation Bのうち、sum(abs(B[i+1]-B[i]-C))を最小化せよ。
またこの値がタイの場合は、辞書順最小のものを求めよ。

解法

Aを昇順にソートしておく。
もしCが0以上なら、B=Aで良い。
以後、Cが負の場合を考える。
sumの最小化だけなら、Aを降順に並べればよい。
しかし今回Bを辞書順最小化したいので、sumが変わらない範囲でBを並べ替えよう。

A[i-1]-A[i+1]≦|C|なら入れ替え可能なので、値を走査しながらどこまで入れ替え可能か見て行くとよい。

int T;
int N,C;
int A[202000],B[202020];
int L[202000],R[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>C;
		FOR(i,N) {
			cin>>A[i];
		}
		sort(A,A+N);
		if(C>=0||N<=1) {
			FOR(i,N) B[i]=A[i];
		}
		else {
			reverse(A,A+N);
			FOR(i,N) L[i]=(i+N-1)%N,R[i]=(i+1)%N;
			
			B[0]=A[0];
			set<pair<int,int>> S;
			for(i=2;i<=N-2;i++) {
				if(A[i-1]-A[i+1]<=-C) S.insert({A[i],i});
			}
			
			FOR(i,N-1) {
				auto it=S.lower_bound({B[i]+C,0});
				if(it==S.end()) {
					x=R[0];
					S.erase({A[x],x});
				}
				else {
					x=it->second;
					S.erase(it);
				}
				B[i+1]=A[x];
				int l=L[x];
				int r=R[x];
				R[l]=r;
				L[r]=l;
				S.erase({A[l],l});
				S.erase({A[r],r});
				if(l&&L[l]&&R[l]&&(A[L[l]]-A[R[l]]<=-C)) S.insert({A[l],l});
				if(r&&L[r]&&R[r]&&(A[L[r]]-A[R[r]]<=-C)) S.insert({A[r],r});
				
			}
		}
		
		
		
		FOR(i,N) cout<<B[i]<<" ";
		cout<<endl;
		
	}
}

まとめ

Upsolve数意外に多いな。