大家好,又见面了,我是全栈君。
题目大意:有一张洞穴地图,要在这个洞穴里面存放水,要求水不能碰到洞穴顶部。如今给出每一个位置的顶部位置和地面高度。问最多能够放多少水
解题思路:根据物理定理,每一段有水的连续区间,水位高度必须相等
所以我们能够求出在同一段连续区间內的水位高度,该水位高度等于最低洞穴顶部的高度。以此为根据,从左到右更新,再从右到左更新,就能够得到每一个位置的水位高度了
#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;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116603.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...