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)


相关推荐

  • 《深入解析Hello,World》 :第三章 java源代码是怎样变成class文件的

    《深入解析Hello,World》 :第三章 java源代码是怎样变成class文件的javac实现原理编译器原理

  • HONOR荣耀50/荣耀50Pro怎么解锁huawei 荣耀50pro屏幕锁开机锁激活设备锁了应该如何强制解除鸿蒙系统刷机解锁方法流程步骤不开机跳过锁屏移除锁定进系统方法经验

    HONOR荣耀50/荣耀50Pro怎么解锁huawei 荣耀50pro屏幕锁开机锁激活设备锁了应该如何强制解除鸿蒙系统刷机解锁方法流程步骤不开机跳过锁屏移除锁定进系统方法经验今天带来一台用户华为荣耀50手机强制清除华为账号锁案例分享,这个台手机是用户公司手机,由于前使用者离职后未能退出手机的华为账号和锁屏密码,导致手机无法使用。自己通过简单的恢复出厂设置后,发现手机有华为账号锁无法激活手机,这才联系到刷机爱好者技术人员,给予远程强制刷机移除华为荣耀60的账号锁。在此提醒广大用户,登录的华为账号建议绑定经常使用的手机号码,防止无法找回密码从而到时手机无法使用。在刷机解锁过程中需要准备以下工具:链接:百度网盘请输入提取码提取码:8888备用下载连接:yun.p

  • java.util.Map——Map集合的常用方法「建议收藏」

    java.util.Map——Map集合的常用方法「建议收藏」Java技术交流群:817997079,欢迎“有志之士”的加入。开发中最常用的就是List集合和Map集合,Map集合是基于java核心类——java.util中的;Map集合用于储存元素对,Map储存的是一对键值(key和value),是通过key映射到它的value;下面介绍的是Map集合的一些经常用到的方法以及代码示例。1.map.size();方法作用:获取map集合类的大小(m…

  • H5文件简介和使用

    H5文件简介和使用H5文件是层次数据格式第5代的版本(HierarchicalDataFormat,HDF5),它是用于存储科学数据的一种文件格式和库文件。接触到这个文件格式也是因为上Coursera深度学习课程的时候,作业用到了。它是由美国超级计算与应用中心研发的文件格式,用以存储和组织大规模数据。目前由非营利组织HDF小组提供支持。目前,很多商业和非商业组织都支持这种文件格式,如Java,MATLAB,P…

  • qmake:高级用法

    qmake:高级用法一、添加新的配置特性特性(features)是*.prf文件中自定义函数和定义的集合(Qt安装目录\mkspecs\features中有很多*.prf文件)。存放特性文件的目录有很多地方,qmake在查找.prf文件时会按以下顺序检查每个目录:在QMAKEFEATURES环境变量中列出的目录中, 在QMAKEFEATURES属性变量中列出的目录中。 在位于mkspecs目录中的features目录中。 在QMAKESPEC环境变量提供的目录下的featu

  • idea启动tomcat控制台乱码_idea tomcat 乱码

    idea启动tomcat控制台乱码_idea tomcat 乱码最近在部署web项目启动tomcat时日志乱码了,很难受,试着很多方法也没有解决,最后的解决方法让我大跌眼镜,故记录一下,建议看到最后:1.修改本地tomcat下conf目录下logging.properties文件内容新增java.util.logging.ConsoleHandler.encoding=GBK2.修改tomcat下bin-catalina.bat文件3.在tomcat的conf-server.xml中修改4.在idea中修改配置ps:如果还是不行,就跟我今天遇到的

发表回复

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

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