AtCoder ABC #181 : E - Transformable Teacher

今回は簡単目な印象。
https://atcoder.jp/contests/abc181/tasks/abc181_e

問題

N人の生徒(奇数)と先生がいる。
各生徒iの身長H[i]が与えられる。
また先生はいくつかの身長の候補Wから身長を選択できる。

先生含む(N+1)人を2人ずつペアにしたとき、各ペアの身長差の総和の最小値を求めよ。

解法

先生とペアにする生徒を総当たりしよう。
その際、先生の身長はペアの生徒のものに最も近いものを選びたいので、Wをソートしておき、二分探索しよう。

あとは残された生徒のペアだが、身長順にソートして隣接する生徒をペアにするとよい。
その際、indexが(0-originで)偶数番目の人の身長は引き算、奇数番目の人の身長は足し算されるので、事前にindexの偶奇毎に累積和を取っておくとよい。

int N,M;
int H[202020],W[202020];
ll S[2][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>H[i];
	}
	sort(H,H+N);
	FOR(i,N) {
		S[0][i+1]=S[0][i];
		S[1][i+1]=S[1][i];
		S[i%2][i+1]+=H[i];
	}
	FOR(i,M) cin>>W[i];
	sort(W,W+M);
	
	ll ret=1LL<<60;
	FOR(i,N) {
		ll p=S[1][i]+S[0][N]-S[0][i+1];
		ll m=S[0][i]+S[1][N]-S[1][i+1];
		x=lower_bound(W,W+M,H[i])-W;
		if(x<M) ret=min(ret,p-m+abs(H[i]-W[x]));
		x--;
		if(x>=0) ret=min(ret,p-m+abs(H[i]-W[x]));
		
	}
	cout<<ret<<endl;
	
}

まとめ

なぜ身長という設定にしたんだろうな。