Codeforces #251 Div2 D. Devu and his Brother

これは本番すんなり解けてよかった。
http://codeforces.com/contest/439/problem/D

問題

N個の整数A[i]とM個の整数B[j]がある。
ここでコスト1を払うと、A[i]またはB[j]のいずれかの値を1つ選び、インクリメントまたはデクリメントできる。

上記処理を行い、A[i]の最小値がB[j]の最大値以上とするのに必要な最小コストを求めよ。

解法

初期状態でA[i]の最小値がB[j]の最大値以上なら何もしなくてよい。
そうでない場合、どこか境界値を決めてA[i]がそれ以上、B[j]がそれ以下になるようにすると良い。

境界値の決め方は、二分探索による方法もあるが、実際はA[i]及びB[j]のどれかになるのでそれらを境界値候補として総当たりしても良い。

A[i]及びB[j]をソートした上で累積和を事前に取っておくと、lower_boundを用いればA[i]xとなるi,jをL=max(N,M)としてO(logL)で求め、そこからコストも求めることができる。

境界値はO(L)通りなので、計算量はソート処理も境界値によるコスト探索もO(L*logL)。

int N,M;
vector<int> A,B;
ll SA[100002],SB[100002];
set<int> C;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>x,A.push_back(x),C.insert(x);
	FOR(i,M) cin>>x,B.push_back(x),C.insert(x);
	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	if(B[M-1]<=A[0]) return _P("0\n");
	FOR(i,N) SA[i+1]=SA[i]+A[i];
	FOR(i,M) SB[i+1]=SB[i]+B[i];
	
	ll ret=1LL<<60;
	ITR(it,C) {
		int tv=*it;
		ll la=0,lb=0;
		int ida=lower_bound(A.begin(),A.end(),tv)-A.begin();
		if(ida>0) la = ida*(ll)tv-SA[ida];
		
		int idb=lower_bound(B.begin(),B.end(),tv)-B.begin();
		if(idb<M) lb = (SB[M]-SB[idb])-(M-idb)*(ll)tv;
		ret=min(ret,la+lb);
	}
	cout << ret << endl;
}

まとめ

lower_bound周りで1ずれるのが怖かったが、今回はすんなり通った。