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
#include
#include
#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
PII;const int N=300010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;LL pre[N],ans=5e18;struct Node{ LL x1,x2; LL x,y;}a[N];bool cmp(Node x,Node y){ if(x.x1!=y.x1) return x.x1
>n>>k>>x1>>y1>>x2>>y2; for(int i=1;i<=n;i++) { LL w,z; scanf("%lld%lld",&w,&z); LL r1=get_dis(w,z,x1,y1); LL r2=get_dis(w,z,x2,y2); a[i]={ r1,r2,w,z}; } sort(a+1,a+1+n,cmp); priority_queue
q1; priority_queue
,greater
>q2; for(int i=n-1;i>=0;i--) { LL t=get_dis(a[i+1].x,a[i+1].y,x2,y2); if(q2.size()
q2.top()) { q1.push(q2.top()); q2.pop(); q2.push(t); } else q1.push(t); if(q1.size()) pre[i]=q1.top(); else pre[i]=0; } } for(int i=0;i<=n;i++) { LL r1=a[i].x1,r2=pre[i]; ans=min(ans,r1+r2); } printf("%lld\n",ans); return 0;}
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
PII;const int N=300010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;LL pre1[N],pre2[N],ans=5e18;struct Node{ LL x1,x2; LL x,y;}a[N];bool cmp1(Node x,Node y){ if(x.x1!=y.x1) return x.x1
>n>>k>>x1>>y1>>x2>>y2; for(int i=1;i<=n;i++) { LL w,z; scanf("%lld%lld",&w,&z); a[i].x=w,a[i].y=z; } for(int i=1;i<=n;i++) { LL r1=get_dis(a[i].x,a[i].y,x1,y1); LL r2=get_dis(a[i].x,a[i].y,x2,y2); a[i].x1=r1,a[i].x2=r2; } sort(a+1,a+1+n,cmp1); priority_queue
q1; priority_queue
,greater
>q2; for(int i=n-1;i>=1;i--) { LL t=get_dis(a[i+1].x,a[i+1].y,x2,y2); if(q2.size()
q2.top())//以防 k==0 RE { q1.push(q2.top()); q2.pop(); q2.push(t); } else q1.push(t); if(q1.size()) pre1[i]=q1.top(); } } for(int i=1;i<=n;i++) { LL r1=a[i].x1,r2=pre1[i]; ans=min(ans,r1+r2); } sort(a+1,a+1+n,cmp2); priority_queue
q3; priority_queue
,greater
>q4; for(int i=n-1;i>=1;i--) { LL t=get_dis(a[i+1].x,a[i+1].y,x1,y1); if(q4.size()
q4.top()) { q3.push(q4.top()); q4.pop(); q4.push(t); } else q3.push(t); if(q3.size()) pre2[i]=q3.top(); else pre2[i]=0; } } for(int i=1;i<=n;i++) { LL r1=a[i].x2,r2=pre2[i]; ans=min(ans,r1+r2); } printf("%lld\n",ans); return 0;}

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/106063606 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:upc 最⼤⼦段和 线段树 + 懒标
下一篇:upc 潜入苏拉玛 多源bfs + 并查集 + 思维

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月21日 04时08分20秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

input js number 整数_JS基础简单小结(1) 2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导 2019-04-21
docker mysql服务启动失败_docker中mysql初始化及启动失败问题解决方案 2019-04-21
mysql 阿里云 添加磁盘空间_rds mysql磁盘空间包含 2019-04-21
mysql 1364 hy000_mysql SQL Error: 1364, SQLState: HY000 保存错误 2019-04-21
mysqli拓展还能用mysql_最近在学习php,其中使用了MYSQLi扩展,注意是MYSQLi不是MYSQL(因PHP7已经不支持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
慕课python第五周测试答案_中国大学MOOC(慕课)_python+_满分章节测试答案 2021-06-24
lsof查看占用高_lsof解决磁盘占用过高,查询却无大文件处理一例! 2021-06-24
python调用oracle过程 权限不足_oracle-存储过程提示 ORA-01031: 权限不足 2021-06-24