IOI 2011-day1 Rice Hub

問題文 : 米集積場 (pdf注意)

解法 :
C(x) : Bバーツ以内でx個の水田から米を届けられるか, とすると,
C(A)が成り立つ時, C(A - 1)も成立する. よって, xについて二分探索を行う.

このとき, 集める水田が連続していたほうがいいことは明らかなので, R - x個の, 連続するx個の水田の集合について, Bバーツ以内で米を届けられる最短地点を探す.
このとき, その集合の中央の水田に集積場をたてることが最適なので, 中央に集めて確認をする.
こうすることで, 米を集められる水田の最大値が求まる.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

int besthub(int R, int L, int *X, ll B)
{
	int left, right, center;
	ll rSum[100000];
	left = 1, right = R;
	
	for (int i = 0; i < R; i++){
		if (!i) rSum[i] = X[i];
		else rSum[i] = rSum[i - 1] + X[i];
	}
	
	while (left != right){
		center = (left + right + 1) / 2;
		bool ok = false;
		for (int i = 0; i <= R - center; i++){
			int a = i, b = i + center - 1;
			int p1 = (a + b) / 2, p2 = (a + b) / 2 + 1;
			ll c1 = p1 - a + 1, c2 = c1 + 1;
			ll cost1 = X[p1] * c1 - (rSum[p1] - (a ? rSum[a - 1] : 0)) + (rSum[b] - (p1 ? rSum[p1] : 0)) - X[p1] * (center - c1);
			ll cost2 = X[p2] * c2 - (rSum[p2] - (a ? rSum[a - 1] : 0)) + (rSum[b] - (p2 ? rSum[p2] : 0)) - X[p2] * (center - c2);
			if (min(cost1, cost2) <= B){
				ok = true;
				break;
			}
		}
		if (ok == true){
			left = center;
		}
		else {
			right = center - 1;
		}
	}
	
	return (left);
}