当前位置:网站首页>UVALive – 4621 Cav 贪心 + 分析「建议收藏」
UVALive – 4621 Cav 贪心 + 分析「建议收藏」
2022-07-07 16:53:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
题目大意:有一张洞穴地图,要在这个洞穴里面存放水,要求水不能碰到洞穴顶部。如今给出每一个位置的顶部位置和地面高度。问最多能够放多少水
解题思路:根据物理定理,每一段有水的连续区间,水位高度必须相等 所以我们能够求出在同一段连续区间內的水位高度,该水位高度等于最低洞穴顶部的高度。以此为根据,从左到右更新,再从右到左更新,就能够得到每一个位置的水位高度了
#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.cn/116603.html原文链接:https://javaforall.cn
边栏推荐
- unity2d的Rigidbody2D的MovePosition函数移动时人物或屏幕抖动问题解决
- 国内的软件测试会受到偏见吗
- Will low code help enterprises' digital transformation make programmers unemployed?
- 基于图像和激光的多模态点云融合与视觉定位
- Desci: is decentralized science the new trend of Web3.0?
- Discuss | what preparations should be made before ar application is launched?
- 直播预约通道开启!解锁音视频应用快速上线的秘诀
- Rules for filling in volunteers for college entrance examination
- Some key points in the analysis of spot Silver
- nest. Database for getting started with JS
猜你喜欢
Learn to make dynamic line chart in 3 minutes!
Three forms of multimedia technology commonly used in enterprise exhibition hall design
Five network IO models
[Tawang methodology] Tawang 3W consumption strategy - U & a research method
Charles+Postern的APP抓包
RIP和OSPF的区别和配置命令
伺服力矩控制模式下的力矩目标值(fTorque)计算
Differences between rip and OSPF and configuration commands
Redis
【C语言】字符串函数
随机推荐
[sword finger offer] 59 - I. maximum value of sliding window
Improve application security through nonce field of play integrity API
“解密”华为机器视觉军团:华为向上,产业向前
I feel cheated. Wechat tests the function of "size number" internally, and two wechat can be registered with the same mobile number
微信网页调试8.0.19换掉X5内核,改用xweb,所以x5调试方式已经不能用了,现在有了解决方案
Antisamy: a solution against XSS attack tutorial
Charles+drony的APP抓包
Desci: is decentralized science the new trend of Web3.0?
Classification of regression tests
RIP和OSPF的区别和配置命令
PTA 1102 教超冠军卷
SQLite SQL exception near "with": syntax error
[Tawang methodology] Tawang 3W consumption strategy - U & a research method
虚拟数字人里的生意经
如何给“不卖笔”的晨光估值?
【Unity Shader】插入Pass实现模型遮挡X光透视效果
静态路由配置
来了!GaussDB(for Cassandra)新特性亮相
【塔望方法论】塔望3W消费战略 - U&A研究法
2022-07-04 matlab读取视频帧并保存