CF938B Run For Your Prize 题解
2024-09-06 02:17:39
Content
有两个人,一个在 \(1\) 处,一个在 \(10^6\) 处,在他们之间有 \(n\) 个奖品,第 \(i\) 个奖品在 \(a_i\) 处。一开始在 \(1\) 处的人每秒可向右移动 \(1\) 个单位,一开始在 \(10^6\) 处的人每秒可向左移动 \(1\) 个单位,我们认为他们经过了礼物就算得到礼物,并且不需要耗费时间,求他们得到所有礼物的最短时间。
数据范围:\(1\leqslant n\leqslant 10^5,1<a_i<10^6\)。
Solution
我们可以将满足 \(1< a_i\leqslant 5\times10^5\) 的奖品都划给在 \(1\) 处的人去取,将满足 \(5\times 10^5< a_i<10^6\) 的奖品都划给在 \(10^6\) 处的人去取,很容易发现这是最优的方案,然后我们看在 \(1\) 处的人取到他要取的最右边的奖品需要耗费的时间和在 \(10^6\) 处的人取到他要取的最左边的奖品需要耗费的时间的较大值,这其实就等同于求距离了。
Code
int n, x, a[100007], b[100007];
int main() {
getint(n);
_for(i, 1, n) {getint(x); if(x >= 1 && x <= 500000) a[++a[0]] = x; else b[++b[0]] = x;}
sort(a + 1, a + a[0] + 1), sort(b + 1, b + b[0] + 1);
int ans = max((a[0] ? a[a[0]] - 1 : 0), (b[0] ? 1000000 - b[1] : 0));
writeint(ans);
return 0;
}
最新文章
- 学习笔记:利用GDI+生成简单的验证码图片
- saiku、mondrian前奏之——立方体、维度、Schema的基本概念
- centos下安装cdh5
- HTML5简单入门系列(九)
- Phone Number 2010年山东省第一届ACM大学生程序设计竞赛
- JavaScript的DOM编程--04--获取元素节点的子节点
- 两道很好的dp题目【4.29考试】
- 【Android Studio安装部署系列】三十四、将Eclipse项目导入到Android Studio中
- mysql的基本操作笔记
- IIS日志分析工具-Log Parser
- shell编程-函数(九)
- Elasticsearch5.4署遇到的问题
- python数据统计量分析
- Linux /etc/password 文件详解
- 大数据入门第十九天——推荐系统与mahout(一)入门与概述
- Go Revel - server.go 源码分析
- oracle EBS上传和下载文件(转)
- PHP相关异常
- struts2中的文件上传和下载
- SQLSERVER 修改实例名以及架构信息
热门文章
- 你有没有觉得邮件发送人固定配置在yml文件中是不妥当的呢?SpringBoot 动态设置邮件发送人
- Qt5 connect 重载信号和槽
- CF1575G GCD Festival
- Codeforces 1288F - Red-Blue Graph(上下界网络流)
- hdu 5552 Bus Routes
- BZOJ 3694&;&;DTOJ 1972: 最短路
- Parallel NetCDF 简介
- Linux基础——常用命令
- micropython1.16官方文档转PDF
- MacBookpro安装VMware Fusion虚拟机,并安装win7 64位系统