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; }