upc spring 对顶堆 + 贪心
发布日期:2021-09-25 23:57:47
浏览次数:5
分类:技术文章
本文共 3726 字,大约阅读时间需要 12 分钟。
spring
时间限制: 1 Sec 内存限制: 128 MB题目描述
A国的森林深处,圣泉的清流正在潺潺流淌⋯⋯ 那是智者所在之地,给即将去往远方的旅者以灵魂的冲洗,小Y也即将在此拭去心灵上的污垢,以纯洁之魂走向重生。 森林很深,不妨把其看作是一个平面直角坐标系。圣泉有两处,一处位于(X1,Y1),另一处位于(X2,Y2)。小Y有n个记忆碎片,第i个位于(xi,yi)。小Y可以给两处圣泉分别设定其半径r1,r2,使得每一个碎片都至少属于一个圣泉的范围之中。 由于小Y身为A国的魔法师,灵魂本就是清澈的,所以他可以向智者请求先拾取不超过k个记忆碎片,然后设定r1,r2,使剩下的那些记忆碎片被两处圣泉所覆盖。 由于圣泉的水是纯洁而不容任何污垢的,所以小Y必须让圣泉的所覆盖的范围尽量小,也就是使r12+r22尽量小。 你作为小Y的挚友,当然愿意帮助他求出这个问题,使他的灵魂得到重生。 输入 第一行共6个整数,n,k,X1,Y1,X2,Y2,含义如题所述。 接下来的n行,每行两个整数xi,yi,表示第i个记忆碎片的位置。 输出 共一行,表示r12+r22的最小值。 样例输入 Copy 3 1 0 0 4 2 0 1 2 2 100 100 样例输出 Copy 5 提示 样例解释 显然先取走第3个记忆碎片,然后令r1=1,r2=2便可覆盖剩下2个记忆碎片。对于100%的数据,0≤k<n≤2×105,|xi|,|yi|≤109。
感觉这个题感觉水水就过去了,我自己也不是很明白为什么这么贪心是正确的
下面说一下我怎么贪的吧。
感觉要让 r1 ^ 2 + r2 ^ 2 最小,我们不能像数学那样直接手写不等式推出来,这可是电脑,那么我们可以分为两种情况:
(1)让 r1 尽可能小的情况下,算出 r2. (2)让 r2 尽可能小的情况下,算出 r1. 感觉如果两种都不是最优情况,那么答案应该是比一种是最优情况大的,基本靠感觉。。 以下说的是第一种情况 怎么让 r1 尽可能小而且枚举起来很方便呢?可以考虑对 r1 排个序,从 1 ~ n 枚举 ,每次的 a [ i ] . r1 就是当前被第一个圣泉包围的半径平方,现在只需要考虑 i + 1 ~ n 的碎片,这些碎片应该被第二个圣泉包围,也就是说,我们要求出 i + 1 ~ n 中,第 k + 1 大的半径平方,这个数可以覆盖掉后面所有碎片,因为可以去掉 k 个嘛,比 k + 1 大的碎片都可以直接去掉。显然求第 k 大数可以用对顶堆来求解,可以预处理一个数组来存,到这推就行了,还要注意假如到了第 i 个点,那么应该算的是第 i + 1 个点与 x2 y2 的距离,因为第 i 个点已经被第一个圣泉覆盖掉了。感谢巨巨的建议,可以把原来的代码改成从0开始,即可枚举所有的情况。
修改过的代码如下:
#include#include #include #include #include
#include#include #include #include #include
转载地址:https://blog.csdn.net/DaNIelLAk/article/details/106063606 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月21日 04时08分20秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
input js number 整数_JS基础简单小结(1)
2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导
2019-04-21
mysql 阿里云 添加磁盘空间_rds mysql磁盘空间包含
2019-04-21
java中gui_java中GUI是什么意思?详细图解
2019-04-21
java iso 8601_如何在iOS上获得ISO 8601日期?
2019-04-21
windows8怎么下载python_win8怎么安装python
2019-04-21
linux猜数字程序,用linux实现猜数字小游戏源码
2019-04-21
linux下堆栈溢出实例,堆栈溢出在Linux上沉默?
2019-04-21
python创建nc文件_工具箱第2期 用python玩转NC
2019-04-21
拆分文件_文件拆分与合并
2019-04-21
开发优势_小程序开发优势好处有哪些
2019-04-21
4光影补丁_我的世界seus光影包
2019-04-21
aria手机下载_Aria2App
2019-04-21
汇编指令msr_ARM汇编:MRS和MSR指令
2019-04-21
lsof查看占用高_lsof解决磁盘占用过高,查询却无大文件处理一例!
2021-06-24