华为机试-水库蓄水问题

题目0242-天然蓄水库
题目描述
公元2919年，人类终于发现了一颗宜居星球——X星。
现想在X星一片连绵起伏的山脉间建一个天热蓄水库，如何选取水库边界，使蓄水量最大？

要求：

山脉用正整数数组s表示，每个元素代表山脉的高度。
选取山脉上两个点作为蓄水库的边界，则边界内的区域可以蓄水，蓄水量需排除山脉占用的空间
蓄水量的高度为两边界的最小值。
如果出现多个满足条件的边界，应选取距离最近的一组边界。
输出边界下标（从0开始）和最大蓄水量；如果无法蓄水，则返回0，此时不返回边界。
例如，当山脉为s=[3,1,2]时，则选取s[0]和s[2]作为水库边界，则蓄水量为1，此时输出：0 2:1
当山脉s=[3,2,1]时，不存在合理的边界，此时输出：0。

#牛客AI配图神器#
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;

//int findun(int arr[100]) {
//int max = 0;
//int k = 0;
//for (int i = 0; i < sizeof(arr) - 1; i++) {
//if (arr[i] > max) {
//max = arr[i];
//k = i;
//}
//}
//return (max, k);
//}
int main() {
string line;
getline(cin, line);
vector<int> height;
stringstream ss(line);
int num;
while (ss >> num) {
height.push_back(num);
}
int n = height.size();
if (n <= 2) {
cout << "0" << endl;
}
//山脉高度
//山脉占用的空间
//最大蓄水量
int left = 0;
int right = n - 1;
int maxwater = 0;
int bestleft = 0;
int bestright = 0;
while (left < right) {
int high = min(height[left], height[right]);
int width = right - left - 1;
if (width > 0) {
int mvolume = 0;
for (int i = left + 1; i < right; i++) {
mvolume += height[i];
}
int wvolume = high * width - mvolume;
if (wvolume > maxwater) {
maxwater = wvolume;
bestleft = left;
bestright = right;
}
}
if (height[left] < height[right]) {
left ++;
}
else{
right --;
}
}
if (maxwater > 0) {
cout << bestleft << " " << bestright << ":" << maxwater << endl;
}
else {
cout << "0" << endl;
}
}