「APIO2015」巴邻旁之桥 Palembang Bridges
2024-10-18 16:36:48
贪心
先转化一下题意
首先如果一个人的家和办公室在河同一侧那么建桥的时候不用去考虑它,最终把答案加上即可
在河两侧的家和办公室互换不影响答案,那么可以把这个抽象到一个区间$[l,r]$,距离就是$|l-x|+|r-x|$
如果$k=1$时,直接取中位数即可
那么考虑$k=2$时,对于某一个人来说,它对答案的贡献就是$min(|l-x_1|+|r-x_1|,|l-x_2|+|r-x_2|)$,$x_1,x_2$为修建两个桥的位置
但是如何快速判断某一个人要走哪个桥,首先如果有一座桥在区间内,那么一定走那座桥,如果没有,那么就走离最近端点最近的那座桥,更本质地讲,就是找离区间中点最近的桥
那么可以根据区间中点将区间排序,然后枚举断点,将左右两端各视作$k=1$时的子问题
现在考虑如何维护一个集合的中位数
发现如果加入或删除某一个数,中位数最多移动$1$个数,那么只需要用set找出每一个当前在序列中的数的前驱后继即可
最新文章
- Mono on CentOS 6.3 安装笔记
- 浅谈Virtual Machine Manager(SCVMM 2012) cluster 过载状态检测算法
- babel6 的 export default bug
- NSXMLParser解析xml格式
- 本地Yum
- iOS6的旋屏控制技巧
- IO 输入流操作
- ASP.NET 为GridView添加序号列,且支持分页连续累计显示
- 什么是json
- EF下CodeFirst、DBFirst与ModelFirst分析
- SIM卡
- JSON 日期格式带 T 问题
- MongoDb的副本集搭建教程(个人操作笔记)
- easyUI带复选框的组合树
- python模块之_pip_其它
- Android热修复原理
- JAVA首次课堂测试总结
- Code Signal_练习题_depositProfit
- javascript 获取当前部署项目路径
- UIScrollView之isTracking delaysContentTouches canCancelContentTouches