UVA 10366 - Faucet Flow（貪心+模擬細節)

Problem E: Faucet Flow

A faucet is pouring water into a long, thin aquarium with various vertical dividers (walls) in it. The aquarium is initially empty, and its bottom is perfectly level. How long will it take for water to spill over its left- or right-most divider? The faucet is above location x=0, and the dividers are located at x=-1, -3, -5, ...,leftx and 1, 3, 5, ..., rightx. The dividers are attached perpendicular to the floor and sides of the aquarium, and have various heights. The aquarium's length is greater than rightx-leftx, its walls are higher than the highest divider, and its width is 1 unit everywhere. Water pours from the faucet at a rate of 1 cubic unit per second. [You may assume that water is an ideal liquid: it always flows downhill and if it cannot flow downhill it spreads at an equal rate in all horizontal directions.]

Input

Each test case consists of two integers leftx (an odd number <= -1) and rightx (an odd number >= 1). Subsequent lines contain the height (a positive integer) of each divider from left to right. There will be no more than 1000 dividers in any test case. Input is terminated with a line containing two zeros.

Output

For each case, output an integer on a single line, indicating how long it will take, in seconds, before water starts spilling over either the left or right divider.

Sample Input

-1 1
3 5
-3 3
4 3 2 1
-3 5
1 2 2 1 1
0 0

Sample Output

6
6
8

題意：給定一些分頻器的高度，從[-1,1]開始注水，問什麼時候漫出去。

思路：惡心的細節題，貪心，找左邊最大的和右邊最高的分隔板，如果相等，時間為中間一塊時間加上兩邊時間少的一塊。如果一邊比較大，那麼最終肯定流到小的那邊，時間計算小的那邊，但是注意還要加上可能流到另一邊的水量，因為如果有分隔板兩邊相等，那麼水流量等於是減半，也可以轉化為，要多流一些水到另一邊，這樣加上這部分的時間即可。

代碼：

#include 
#include 
#define min(a,b) ((a)<(b))?(a):(b)
const int N = 2005;

int l, r, f[N], lv, rv, lmax, rmax, O;

void init() {
	O = -l;
	for (int i = l; i <= r; i += 2)
		scanf("%d", &f[i + O]);	
	lv = -1, rv = 1, lmax = f[lv + O], rmax = f[rv + O];
}

int solve() {
	int ans = 0, i, lt = 0, rt = 0;
	for (i = -1; i >= l; i -= 2) {
		if (f[i + O] > lmax) {
			lmax = f[i + O];
			lv = i;
		}
	}
	for (i = 1; i <= r; i += 2) {
		if (f[i + O] > rmax) {
			rmax = f[i + O];
			rv = i;
		}
	}
	int ll = l;
	for (i = l; i <= lv; i += 2) {
		if (f[i + O] >= f[ll + O]) {
			lt += (i - ll) * f[ll + O];
			ll = i;
		}
	}
	int rr = r;
	for (i = r; i >= rv; i -= 2) {
		if (f[i + O] >= f[rr + O]) {
			rt += (rr - i) * f[rr + O];
			rr = i;
		}
	}
	if (lmax == rmax)
		ans = (rv - lv) * lmax + (min(lt, rt)) * 2;
	else {
		if (lmax > rmax) {
			for (i = -1; i >= l; i -= 2)
				if (f[i + O] >= rmax) {
					lmax = f[i + O]; lv = i;
					break;
				}
			if (lmax == rmax) {
				int lvv = lv;
				for (i = lv; i >= l; i -= 2) {
					if (f[i + O] > rmax) {
						lmax = f[i + O]; lvv = i;
						break;
					}
				}
				ans = (rv - lv) * rmax + (min((lv - lvv) * rmax, rt)) + rt;
			}
			else ans = rmax * (rv - lv) + rt;
		}
		else {
			for (i = 1; i <= r; i += 2)
				if (f[i + O] >= lmax) {
					rmax = f[i + O]; rv = i;
					break;
				}
			if (lmax == rmax) {
				int rvv = rv;
				for (i = rv; i <= r; i += 2) {
					if (f[i + O] > lmax) {
						rmax = f[i + O]; rvv = i;
						break;
					}
				}
				ans = (rv - lv) * lmax + (min((rvv - rv) * lmax, lt)) + lt;

			}
			else ans = lmax * (rv - lv) + lt;
		}
	}
	return ans;
}

int main() {
	while (~scanf("%d%d", &l, &r) && l || r) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}