Codeforces #714 Div2 : F. Swapping Problem

本番ではテストケース40まで来て落とした…。
https://codeforces.com/contest/1513/problem/F

問題

長さNの2つの整数列A,Bが与えられる。
Bのうち、1回だけ2要素をswapできるものとする。
sum(abs(A[i]-B[i]))の最小値を求めよ。

解法

A[i]が昇順になるようソートした場合を考える。
i＜jであるB[i]とB[j]のswapにより総和が小さくなるのは、A[i]≦B[j]＜B[i]≦A[j]のケースである。
A[i]＜B[i]となるiに関し、(A[i],B[i])の対を管理しよう。その際、A[i]≦A[x]≦B[x]≦B[i]となるxは、swap対象として選ばれることはないので、multisetなど使いB[i]が昇順となるように管理する。
あとは逆にA[j]＜B[j]となるjに関し、上記(A[i],B[i])の対のうちB[j]＜B[i]≦A[j]となる最大のB[i]を選ぼう。

A[i],B[i]の符号を反転させたり、AとBをswapさせたりするケースも行っておくと安全。

int N;
pair<int,int> P[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll S=0;
	
	FOR(i,N) {
		cin>>P[i].second;
	}
	FOR(i,N) {
		cin>>P[i].first;
		S+=abs(P[i].first-P[i].second);
	}
	ll ret=S;
	FOR(x,4) {
		sort(P,P+N);
		multiset<pair<int,int>> up;
		multiset<int> Bs;
		int LB=1000000001;
		FOR(i,N) {
			if(P[i].first>=P[i].second) {
				while(up.size()&&up.begin()->first<P[i].first) {
					Bs.erase(Bs.find(up.begin()->second));
					up.erase(up.begin());
				}
				if(Bs.size()) {
					y=max(P[i].second,*Bs.begin());
					ret=min(ret,S-2*(P[i].first-y));
				}
				
			}
			if(P[i].first<=P[i].second) {
				up.insert({P[i].second,P[i].first});
				Bs.insert(P[i].first);
			}
		}
		
		if(x==1) {
			FOR(i,N) swap(P[i].first,P[i].second);
		}
		if(x==0||x==2) {
			FOR(i,N) {
				P[i].first=1000000001-P[i].first;
				P[i].second=1000000001-P[i].second;
			}
		}
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

本番はsetとmultisetの使い分けミスで落とした…。