CSAcademy Round #28 : D. Water Bottles

全完はしたものの、かなり手間取った。
https://csacademy.com/contest/round-28/task/water-bottles/

問題

N個のボトルがありそれぞれ[A[i],B[i]]の範囲で整数リットルの水を入れたい。
全体で合計Lリットルの水をこれらのボトルに入れる際、ボトル間の水量の最大値と最小値の差を最小化せよ。

解法

Editorialは二分探索っぽいけど別解法を紹介。

A同士・B同士をそれぞれ昇順にソートしてしまってもA[i]＜B[i]の関係は保たれるので問題ない。

• A[N-1]≦B[0]の場合
  • A[N-1]*N≦L≦B[0]*Nの場合、各ボトルに均等に水を入れることができる。LがNの倍数でない場合、1リットルだけ差ができる
  • B[0]*N＜Lの場合、全ボトルにB[0]だけ水を入れ、残り(L-B[0]*N)リットルを各ボトルに分配する。
  • L＜A[N-1]*Nの場合、全ボトルにA[N-1]だけ水を入れ、残り不足分(A[N-1]*N-L)リットルをどこから減らすか、というのを各ボトルに分配する。
• A[N-1]≧B[0]
  • 全ボトルで最小値はB[0]以下、最大値はA[N-1]以上であることは確実である。よって、その範囲で各ボトルに入れられる水の範囲にLが含まれるなら、A[N-1]-B[0]が解である。
  • それでは足りない場合、すなわちL＞sum(max(B[i],A[N-1]))の場合、全ボトルにmax(B[i],A[N-1])だけ水を入れ、残りの水を各ボトルに分配する。
  • 逆に過剰である場合、すなわちL＜sum(min(B[0],A[i]))の場合、全ボトルにmin(B[0],A[i])だけ水を入れ、過剰分をどこから減らすか、というのを各ボトルに分配する。

不足分・過剰分の分配処理はいずれも同じで、できるだけ均等に配分することで最大値と最小値の差を抑えることができる。

int N;
ll L;
ll A[101010],B[101010];

ll maA,miB;
ll num[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	maA=0;
	miB=1<<30;
	
	cin>>N>>L;
	FOR(i,N) {
		cin>>A[i]>>B[i];
	}
	sort(A,A+N);
	sort(B,B+N);
	
	vector<ll> V;
	ll ret=0;
	if(A[N-1]>=B[0]) {
		ll C=0,D=0;
		FOR(i,N) {
			C+=max(B[0],A[i]);
			D+=min(A[N-1],B[i]);
		}
		
		if(C<=L && L<=D) {
			cout<<A[N-1]-B[0]<<endl;
			return;
		}
		else if(L<C) {
			L=C-L;
			FOR(i,N) V.push_back(max(0LL,B[0]-A[i]));
		}
		else {
			L=L-D;
			FOR(i,N) V.push_back(max(0LL,B[i]-A[N-1]));
		}
		ret += A[N-1]-B[0];
	}
	else {
		ll C=0,D=0;
		FOR(i,N) {
			C+=max(B[0],A[i]);
			D+=min(A[N-1],B[i]);
		}
		
		if(D<=L && L<=C) {
			cout<<(L%N>0)<<endl;
			return;
		}
		else if(L>C) {
			L=L-C;
			FOR(i,N) V.push_back(B[i]-B[0]);
		}
		else {
			L=D-L;
			FOR(i,N) V.push_back(max(0LL,A[N-1]-A[i]));
		}
	}
	
	sort(ALL(V));
	x=0;
	FOR(i,V.size()) num[V.size()-i]+=V[i]-x, x=V[i];
	for(i=N;i>=1;i--) {
		if(i*num[i]>=L) {
			ret += (L+(i-1))/i;
			break;
		}
		else {
			L-=i*num[i];
			ret+=num[i];
		}
	}
	
	
	cout<<ret<<endl;
}

まとめ

もっときれいに書けるのかな。