UVa10366 Faucet Flow [思维模拟]

Author Avatar
ajcxsu 2018年06月19日
  • 32 次阅读

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

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://acxblog.site/archives/sol-uva-10366.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。