uva10366 Faucet Flow

每次找到两边离中心最高的板，如果等，再找外围的最高版...
画图便于理解
两边先找到距离（-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 ;

}

巴特西

uva10366 Faucet Flow

最新文章

热门文章