当前位置:网站首页>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
边栏推荐
- 【软件测试】从企业版BOSS直聘,看求职简历,你没被面上是有原因的
- The live broadcast reservation channel is open! Unlock the secret of fast launching of audio and video applications
- 链式二叉树的基本操作(C语言实现)
- 3.关于cookie
- 线程池的拒绝策略
- A few simple steps to teach you how to see the K-line diagram
- [sword finger offer] 59 - I. maximum value of sliding window
- 嵌入式C语言程序调试和宏使用的技巧
- socket編程之常用api介紹與socket、select、poll、epoll高並發服務器模型代碼實現
- AntiSamy:防 XSS 攻击的一种解决方案使用教程
猜你喜欢
Antisamy: a solution against XSS attack tutorial
3. About cookies
Wireshark analyzes packet capture data * cap
微信网页调试8.0.19换掉X5内核,改用xweb,所以x5调试方式已经不能用了,现在有了解决方案
单臂路由和三层交换的简单配置
将模型的记忆保存下来!Meta&UC Berkeley提出MeMViT,建模时间支持比现有模型长30倍,计算量仅增加4.5%...
卖空、加印、保库存,东方甄选居然一个月在抖音卖了266万单书
Continuous test (CT) practical experience sharing
链式二叉树的基本操作(C语言实现)
Industry case | digital operation base helps the transformation of life insurance industry
随机推荐
Reject policy of thread pool
unity2d的Rigidbody2D的MovePosition函数移动时人物或屏幕抖动问题解决
小程序中实现付款功能
CVPR 2022丨学习用于小样本语义分割的非目标知识
Improve application security through nonce field of play integrity API
What is the general yield of financial products in 2022?
Skills of embedded C language program debugging and macro use
Discuss | what preparations should be made before ar application is launched?
二叉树的基本概念和性质
磁盘存储链式的B树与B+树
小试牛刀之NunJucks模板引擎
2022-07-04 matlab reads video frames and saves them
pip相关命令
AntiSamy:防 XSS 攻击的一种解决方案使用教程
PTA 1101 B是A的多少倍
Wireshark analyzes packet capture data * cap
Complete e-commerce system
卖空、加印、保库存,东方甄选居然一个月在抖音卖了266万单书
Basic operation of chain binary tree (implemented in C language)
coming! Gaussdb (for Cassandra) new features appear