大家好，又见面了，我是全栈君。
题目大意：有一张洞穴地图，要在这个洞穴里面存放水，要求水不能碰到洞穴顶部。如今给出每一个位置的顶部位置和地面高度。问最多能够放多少水
解题思路：根据物理定理，每一段有水的连续区间，水位高度必须相等
所以我们能够求出在同一段连续区间內的水位高度，该水位高度等于最低洞穴顶部的高度。以此为根据，从左到右更新，再从右到左更新，就能够得到每一个位置的水位高度了
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1000010;
const int INF = 0x3f3f3f3f;
int s[N], p[N], n;
void init() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &p[i]);
}
for(int i = 0; i < n; i++) {
scanf("%d", &s[i]);
}
}
int solve() {
int t = INF;
for(int i = 0; i < n; i++) {
t = min(t, s[i]);
t = max(t, p[i]);
s[i] = t;
}
t = INF;
for(int i = n - 1; i >= 0; i--) {
t = min(t, s[i]);
t = max(t, p[i]);
s[i] = t;
}
int ans = 0;
for(int i = 0; i < n; i++)
ans += s[i] - p[i];
return ans;
}
int main() {
int test;
scanf("%d", &test);
while(test--) {
init();
printf("%d\n", solve());
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116603.html原文链接：https://javaforall.net
