UVALive – 4621 Cav 贪心 + 分析「建议收藏」

UVALive – 4621 Cav 贪心 + 分析

大家好,又见面了,我是全栈君。

题目大意:有一张洞穴地图,要在这个洞穴里面存放水,要求水不能碰到洞穴顶部。如今给出每一个位置的顶部位置和地面高度。问最多能够放多少水

解题思路:根据物理定理,每一段有水的连续区间,水位高度必须相等
所以我们能够求出在同一段连续区间內的水位高度,该水位高度等于最低洞穴顶部的高度。以此为根据,从左到右更新,再从右到左更新,就能够得到每一个位置的水位高度了

#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账号...

(0)


相关推荐

  • com组件与dll的区别_组件对象模型

    com组件与dll的区别_组件对象模型这阵子在想一个需要利用com组件的小程序怎么做,突然想起上次去面试的时候考官问过autocad开发时为什么要利用com,而不采用一般的dll呢?   到google上查了一下,许多人也问了一样的问题:)   用com来写程序要比普通的dll麻烦一些,但是带来的好处也大很多,尤其是在开发像autocad这样大型软件的时候,需要跨区域来协同工作。 “学习COM,首先要知道COM的目的是什么,它

    2022年10月23日
  • 如何查看被占用的端口_java端口被占用怎么解决

    如何查看被占用的端口_java端口被占用怎么解决一、通过命令查找端口被谁占用1、开始—->运行—->cmd,或者是window+R组合键,调出命令窗口2、输入命令:netstat-ano,列出所有端口的情况。在列表中我们观察被占用的端口,比如是49157,首先找到它。3、查看被占用端口对应的PID,输入命令:netstat-aon|findstr”49157″,回车,记下最后一位数字,即PID,这里是27204、继续输…

  • loadrunner压力测试学习笔记

    loadrunner压力测试学习笔记loadrunner学习过程以下仅记录自己的学习过程,有不对之处欢迎指出。压力测试步骤:1.分析需求2.准备脚本3.调试脚本2.准备脚本:可以录制也可以自己写,录制的话先按需求分好每一个action,录制时先切换到当前action,再进行录制。例如:创建一个新的脚本,在action里添加新的action,open_index,submit_login,sign_off(loadrunner自带案例的登录过程)3.调试脚本:(1)回放:脚本准备好后进行回放,需要参数的提前准备好参数,比如注册

  • ioctl之FIONREAD

    ioctl之FIONREAD在学习ioctl时常常跟read,write混淆。其实ioctl是用来设置硬件控制寄存器,或者读取硬件状态寄存器的数值之类的。而read,write是把数据丢入缓冲区,硬件的驱动从缓冲区读取数据一个个发送或者把接收的数据送入缓冲区。 ioctl(keyFd,FIONREAD,&b)得到缓冲区里有多少字节要被读取,然后将字节数放入b里面。接下来就可以

  • java注解生成xml和包含CDATA问题

    百度java生成xml,有一大推的文章,主要的生成方式一种使用Dom4J ,还有一种使用Jdk自带注解类! 下面主要整理我注解类的使用,(可以参考这篇文章Dom4J生成xml和包含CDATA问题)和xml中CDATA 问题的解决方法!

  • information leakage._information interview

    information leakage._information interviewhttps://www.owasp.org/index.php/Information_LeakageExamplesExample1Thefollowingcodeprintsthepathenvironmentvariabletothestandarderrorstream: char*path=getenv(“PATH”); …

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号