# 11550: 【原1550】留下的水

### 题目描述

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

## 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单位）
``````

## 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;
}
``````