用最优美的方法最简洁地处理掉所有情况。

Problem

给 n 个板，分隔出 n - 1 个格子，每个板有高度，每个格子宽为 2。
从中间开始滴水，每秒滴体积为 1 的水，问从什么时候开始最左边或最右边漏水。

Solution

找右边最高的最靠近中间的板。
找左边最高的最靠近中间的板。

讨论即可。

剩下的细节请看代码。

Code

// Code by ajcxsu
// Problem: faucet flow

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int blo[N];

int main() {
    ios::sync_with_stdio(false);
    int l, r;
    while(cin>>l>>r, l) {
        int n=(abs(l)+r)/2+1;
        int nl=(abs(l)+1)/2, nr=nl+1;
        for(int i=1;i<=n;i++) cin>>blo[i];
        int lh=0, rh=0, lpos, rpos;
        for(int i=nl;i>=1;i--)
            if(blo[i]>lh) lh=blo[i], lpos=i;
        for(int i=nr;i<=n;i++)
            if(blo[i]>rh) rh=blo[i], rpos=i;
        if(lh==rh) {
            int lcos=0, rcos=0;
            for(int i=1, j=0; i<lpos; i++)
                j=max(j, blo[i]), lcos+=j;
            for(int i=n, j=0; i>rpos; i--)
                j=max(j, blo[i]), rcos+=j;
            cout<<(rpos-lpos)*lh*2+min(lcos, rcos)*4<<endl;
        }
        else {
            int v=min(lh, rh);
            while(blo[nl]<v) nl--;
            while(blo[nr]<v) nr++;
            int lcos=0, rcos=0;
            if(rh>lh) {
                for(int i=nr, j=0; blo[i]<=lh; i++)
                    j=max(j, blo[i]), rcos+=j;
                for(int i=1, j=0; i<nl; i++)
                    j=max(j, blo[i]), lcos+=j;
            }
            else {
                for(int i=nl, j=0; blo[i]<=rh; i--)
                    j=max(j, blo[i]), rcos+=j;
                for(int i=n, j=0; i>nr; i--)
                    j=max(j, blo[i]), lcos+=j;
            }
            int ret=(lcos+min(lcos, rcos))*2;
            ret+=(nr-nl)*v*2;
            cout<<ret<<endl;
        }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-uva-10366.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆