每次找到两边离中心最高的板,如果等,再找外围的最高版...
画图便于理解
两边先找到距离(-1,1)最近的最大值L和R,因为可能存在多个最高的挡板。
接着比较两个L和R的大小,相等的话分别分析两边,取最小值
注意L和R一边高的话两边都会流,所以这块的时间要乘2。
比如分析右边,从最外围开始,顶部画平行线往内部走,就发现分成了几个区间,加起来就可以了。
L,R不等的话,(这里出现了一个坑),高的那边可能有比低的那边高的其他边;然后又有一个坑,可能找到的边和低的那个边等高

#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int N = ;
int l, r, x[N], y[N];
int L, R, idl, idr; void read() {
R = L = ;
for (int i = l; i <= r; i += ) {
if (i < ) {
scanf("%d", &x[(-i)/]);
if (L <= x[(-i)/]) {
L = x[(-i)/]; idl = (-i)/;
}
}
else {
scanf("%d", &y[i/]);
if (R < y[i/]) {
R = y[i/]; idr = i/;
}
}
}
return ;
} int solve() {
l = (-l) / ; r = r / ;
int tmp;
if (R == L) {
int k = , t = ;
tmp = x[l];
for (int i = l; i > idl; i--) {
k += tmp; tmp = max(tmp, x[i-]);
}
tmp = y[r];
for (int i = r; i > idr; i--) {
t += tmp; tmp = max(tmp, y[i-]);
} return (idl + idr + ) * R * + min(k, t) * * ;//*2*2因为要从中间分开流
} else {
int T = min(R, L);
int p = , q = , k = , t = ;
while (p < l && x[p] < T) p++;
while (q < r && y[q] < T) q++; if (R > L) {
tmp = y[q];
for (int i = q; y[i] <= L; i++) {
k += tmp; tmp = max(tmp, y[i+]);
}
tmp = x[l];
for (int i = l; i > p; i--) {
t += tmp; tmp = max(tmp, x[i-]);
} } else {
tmp = x[p];
for (int i = p; x[i] <= R; i++) {
k += tmp; tmp = max(tmp, x[i+]); //k是从另一边流(如果开始找到的边高度等于T),直到遇到高于T的
}
tmp = y[r];
for (int i = r; i > q; i--) {
t += tmp; tmp = max(tmp, y[i-]);
}
}
int ans = t> k ? t + k : * t; //t<k,说明确实要分开流,从T那边流走的时间;t>k,(总体积2*k+2*k+2*(t-k))
return ans * + (p + q + ) * T * ;
}
} int main() {
while (scanf("%d%d", &l, &r) == && l && r) {
read();
printf("%d\n", solve());
}
return ;
}
05-11 20:18