uva1442

题意：向一个洞穴里面灌水，使得水不会触碰到顶（可以无限接近），最多可以灌多少。

分析：从左往右搜索，寻找最合适水位，从右往左搜索，寻找最合适水位。

1.如果顶点小于水位，说明要降水位水位=顶点。

2.如果底端大于水位，说明水被隔断，要升水位，水位=底端。

#include#includeusing namespace std;const int maxn = 1000000 + 5;int n, p[maxn], s[maxn], h[maxn];int main() {int T;scanf("%d", &T);while(T--) {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 ans = 0, level = s[0];for(int i = 0; i < n; i++) {if(p[i] > level) level = p[i];if(s[i] < level) level = s[i];h[i] = level;}level = s[n-1];for(int i = n-1; i >= 0; i--) {if(p[i] > level) level = p[i];if(s[i] < level) level = s[i];ans += min(h[i], level) - p[i];}printf("%d\n", ans);}return 0;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！