Skip to content

11550: 【原1550】留下的水

题目

题目描述

author: Leetcode 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1550

Description

下雨了，由于地面坑坑洼洼所以存了不少的水，小明很好奇，想看看一共留下了多少水（只考虑每个纵截面留存水的面积）。

给出n个非负整数代表每单位宽度横坐标的高度，请计算一共可以接下多少的水。

Input Format

共两行。

第1行：n(1<=n<=1000)，代表横坐标总个数。

第2行：共n个非负整数xi(1<=xi<=10000)，以数组形式出现.

如[1,2,3,4,5,6]代表从坐标0到坐标5的高度分别为1,2,3,4,5,6。

Output Format

一个整数，代表留下的水的量。

Sample Input

12
[0,1,0,2,1,0,1,3,2,1,2,1]

Sample Output

6
（解释：1,0,2之间存留单位的水；2,1,0,1,3之间存留4单位的水；2,1,2之间存留1单位的水。总共6单位）

hint

BugenZhao's solution 

//
// Created by BugenZhao on 2019/3/18.
//
// 以最高处二分

#include <iostream>
#include <vector>

using namespace std;

static const auto _____ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

int trap(vector<int> &height) {
    int max_height = 0, max_index = 0, ans = 0;
    for (int i = 0; i != height.size(); ++i)
        if (height[i] > max_height)
            max_height = height[i], max_index = i;
    max_height = 0;
    for (int i = 0; i < max_index; ++i)
        if (max_height > height[i])
            ans += max_height - height[i];
        else
            max_height = height[i];
    max_height = 0;
    for (int i = height.size() - 1; i > max_index; --i)
        if (max_height > height[i])
            ans += max_height - height[i];
        else
            max_height = height[i];
    return ans;
}

int main() {
    int N;
    cin >> N;
    vector<int> height(N);
    char tmp;
    cin >> tmp;
    for (int i = 0; i < N; ++i) {
        cin >> height[i];
        cin >> tmp;
    }
    cout << trap(height) << endl;
    return 0;
}

FineArtz's solution 

/* 留下的水 */
#include <iostream>
#include <cstring>
using namespace std;

int n;
char ch;
int a[1005] = {0}, maxx = 0, ans = 0;

int main(){
    cin >> n;
    int num = 0, cnt = 0;
    bool flag = false;
    while (cin >> ch){
        if (!isdigit(ch)){
            if (flag){
                a[++cnt] = num;
                if (num > maxx)
                    maxx = num;
                num = 0;
                flag = false;
            }
            continue;
        }
        flag = true;
        num = num * 10 + ch - '0';
    }
    int l = 1, r = n;
    for (int h = 1; h <= maxx; ++h){
        while (a[l] < h)
            ++l;
        while (a[r] < h)
            --r;
        for (int i = l; i <= r; ++i)
            if (a[i] < h)
                ++ans;
    }
    cout << ans << endl;
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cstdio"
using namespace std;

int xi[1009] = { 0 };

int main() {
    int n;
    scanf("%d\n[", &n);

    for (int i = 0; i < n - 1; ++i)
        scanf("%d,", &xi[i]);
    scanf("%d]", &xi[n - 1]);

    int lpos = 0, rpos = 1, stock_num = 0, ans = 0;
    for (; rpos < n; ++rpos) {
        if (xi[rpos] >= xi[lpos]) {
            ans += xi[lpos] * (rpos - lpos - 1) - stock_num;
            lpos = rpos;
            stock_num = 0;
        }
        else if (rpos == n - 1) {
            //倒序
            stock_num = 0;
            for (int last_rpos = n - 1, last_lpos = n - 2; last_lpos >= lpos; --last_lpos) {
                if (xi[last_lpos] >= xi[last_rpos]) {
                    ans += xi[last_rpos] * (last_rpos - last_lpos - 1) - stock_num;
                    last_rpos = last_lpos;
                    stock_num = 0;
                }
                else {
                    stock_num += xi[last_lpos];
                }
            }
        }
        else {
            stock_num += xi[rpos];
        }
    }

    cout << ans;

    return 0;
}

Neight99's solution 

#include <iostream>

using namespace std;

const int maxN = 1e4 + 100;
int height[maxN] = {0};
char input[maxN] = {0};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int k = 0, N, maxHeight = 0, distance = 0;
    long long waterSum = 0;
    bool flag = 0;
    char *ch;
    cin >> N;
    cin >> input;

    ch = input;
    while (*ch) {
        if (*ch >= '0' && *ch <= '9') {
            int temp = 0;
            while (*ch >= '0' && *ch <= '9') {
                temp *= 10;
                temp += (*ch - '0');
                ch++;
            }
            height[k] = temp;
            if (height[k] > maxHeight) {
                maxHeight = height[k];
            }
            k++;
        }
        ch++;
    }

    for (int i = 0; i < maxHeight; i++) {
        int j;
        for (j = 0, flag = 0, distance = 0; j < N; j++) {
            if (height[j] > i && flag == 0) {
                flag = 1;
            } else if (height[j] <= i && flag == 1) {
                distance++;
            }
            if (height[j] > i && flag == 1) {
                waterSum += distance;
                distance = 0;
            }
        }
    }

    cout << waterSum;

    return 0;
}

q4x3's solution 

/**
 * 模拟
 * 记录最左边的高度，向右扫描
 * 扫到更高的更新水量和最高高度
 * 右往左也要扫一遍
 * 扫到之前最高点停止
 * 注意同高度处理
 **/
#include <iostream>

using namespace std;

int n, a[1233], ans, cur, curind;
char tmp;
int main() {
    cin >> n;
    for(int i = 0;i < n;++ i) {
        cin >> tmp;
        cin >> a[i];
    }
    cin >> tmp;
    cur = a[0];
    for(int i = 1;i < n;++ i) {
        if(a[i] >= cur) {
            ans += cur * (i - curind - 1);
            for(int j = curind + 1;j < i;++ j) {
                ans -= a[j];
            }
            cur = a[i];
            curind = i;
        }
    }
    int maxi = curind;
    cur = a[n - 1]; curind = n - 1;
    for(int i = n - 2;i >= maxi;-- i) {
        if(a[i] >= cur) {
            ans += cur * (curind - i - 1);
            for(int j = curind - 1;j > i;-- j) {
                ans -= a[j];
            }
            cur = a[i];
            curind = i;
        }
    }
    cout << ans << endl;
}

skyzh's solution

#include<iostream>
using namespace std;

int D[2000];
int L[2000] = { 0 }, R[2000] = { 0 };

int main() {
    int N;
    int unit = 0;
    cin >> N; while (cin.get() != '[');
    for (int i = 0; i < N; i++) {
        cin >> D[i];
        cin.get();
    }
    L[0] = 0;
    for (int i = 1; i <= N; i++) {
        L[i] = max(L[i - 1], D[i - 1]);
    }
    R[N] = 0;
    for (int i = N - 1; i >= 0; i--) {
        R[i] = max(R[i + 1], D[i]);
    }
    for (int i = 0; i < N; i++) {
        int H = min(L[i], R[i + 1]);
        unit += max(0, H - D[i]);
    }
    cout << unit << endl;
    return 0;
}

victrid's solution 

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    char tm;
    int* hgt  = new int[n];
    int* llm  = new int[n];
    int* rrm  = new int[n];
    int water = 0;
    for (int i = 0; i < n; i++) {
        cin >> tm;
        cin >> hgt[i];
    }
    cin >> tm;
    //每个点判断能够达到的高度
    int l = 0, r = n - 1;
    llm[0] = hgt[0];
    for (int i = 1; i < n; i++) {
        llm[i] = hgt[i] > llm[i - 1] ? hgt[i] : llm[i - 1];
    }
    rrm[n - 1] = hgt[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        rrm[i] = hgt[i] > rrm[i + 1] ? hgt[i] : rrm[i + 1];
        water += (llm[i] > rrm[i] ? rrm[i] : llm[i]) - hgt[i];
    }
    cout << water;
}

WashSwang's solution 

#include <iostream>
using namespace std;
int n,x,ans,cur,h[2000],num,lmax[2000],rmax[2000];
char c;
int main() {
    cin>>n;
    while (cin>>c){
        if (c=='[') continue;
        if (c==']') {h[num++]=cur; break;}
        if (c==',') {h[num++]=cur; cur=0;}
        else cur=cur*10+c-48;
    }
    for (int i=1;i<n;++i) lmax[i]=max(lmax[i-1],h[i-1]);
    for (int i=n-2;i>=0;--i) rmax[i]=max(rmax[i+1],h[i+1]);
    for (int i=0;i<n;++i) ans+=max(min(rmax[i],lmax[i]),h[i])-h[i];
    cout<<ans;
    return 0;
}

yyong119's solution 

#include <iostream>
using namespace std;

int height[1001];
int leftH[1001];

int main() {
    int n;
    cin >> n;
    char eat;
    for (int i = 1; i <= n; ++i) {
        cin >> eat >> height[i];
        leftH[i] = (leftH[i - 1] < height[i] ? height[i] : leftH[i - 1]);
    }
    int rightH = height[n];
    int ans = 0;
    for (int i = n - 1; i >= 1; --i) {
        int min = (leftH[i - 1] < rightH ? leftH[i - 1] : rightH);
        if (height[i] < min) ans += min - height[i];
        else rightH = height[i];
    }
    cout << ans << endl;
    return 0;
}