uva 1442:Cave(贪心)
2024-09-04 15:52:13
题意:一个洞穴长n,告诉你每个位置的地面高度和顶部高度,让你往里灌水,要求水不能碰到天花板(但可以无限接近)。求最多的水量。(洞穴两边视为封闭)
思路:如果知道一个位置向左看最高可以多高,向右看最高可以多高,就可以知道这个位置最终的高度了。方法是扫两次。每次扫的时候,定义一个之前最高值。若之前最高值高于现在的顶,则下降至顶。若低于底,则上升至底(因为后面的这种高度能被这个底挡住)。如果在中间则不用变。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define N 1000010 int p[N];
int s[N]; int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = ; i < n; i++) {
scanf("%d", &p[i]);
}
for (int i = ; i < n; i++) {
scanf("%d", &s[i]);
} int tmp = 0x3f3f3f3f;
for (int i = ; i < n; i++) {
tmp = min(tmp, s[i]);
tmp = max(tmp, p[i]); s[i] = tmp;
} tmp = 0x3f3f3f3f;
for (int i = n-; i >= ; i--) {
tmp = min(tmp, s[i]);
tmp = max(tmp, p[i]); s[i] = tmp;
} int ans = ;
for (int i = ; i < n; i++) {
ans += s[i]-p[i];
}
printf("%d\n", ans);
}
return ;
}
最新文章
- ArcEngine拓扑
- centos之开放80端口
- Jeff Somers&#39;s N Queens Solutions 最快的n皇后算法
- 开发机上绕过Chrome同源策略的办法
- char 数组和 int 之间转化
- lintcode :数组剔除元素后的乘积
- android activity启动的时候隐藏软键盘
- paip.QQ音乐导出歌单总结
- Qt5:QSystemTrayIcon类实现程序托盘图标
- Azure按订阅,资源组,资源类型导出所有资源powershell命令
- idea设置JVM运行参数
- 100-days: twelve
- ASP.NET 前端Ajax获取数据并刷新
- Confluence 6 使用 LDAP 授权连接一个内部目录 - 用户 Schema 设置
- 20145203盖泽双 《Java程序设计》第6周学习总结
- Shell编写8点建议
- Git 配置ssh key的步骤
- No serializer found for class org.hibernate.proxy.pojo.javassist.JavassistLazyInitializer解决方法
- 20145209刘一阳 《网络对抗》Exp7 网络欺诈技术防范
- Python 对象模型 -- (转)
热门文章
- 使用virtualbox安装的Ubuntu,窗口分辨率过小,使用增强工具完成和vmtools一样的功能。
- OWINS是什么(转载)
- Android 线程那些事儿
- Java语言基础---逻辑运算(长路短路运算)
- P1880 石子合并
- easyui datagrid复选框控制单选
- Oracle 学习笔记(十)
- ansible Failed to connect to the host via ssh: no such identity: /root/.ssh/id_rsa.bak
- var和function定义方法的区别
- WMS请求GetCapabilities,变成下载mapserv.exe解决办法