题解 | #带权中位数#
带权中位数
https://ac.nowcoder.com/acm/problem/284613
笔记
解法一：
- 结论：人数刚刚过半的那个点就是目标点
- 证明：
- 实现：统计每个点的人数，然后对其求前缀和
解法二：
先求出所有人到一号点的总路程，然后计算目标点从1变成2的时候的总路程的变化量来计算目标点为2时的总路程。
dist(x+1) = dist(x) + (Px+1 - Px) * (x及其之前的人数 - x+1及其之后的人数)
02-04 16:06 武汉理工大学 算法工程师 发布于山西
关注
全部评论
相关推荐
点赞 评论 收藏
分享
01-19 12:48
门头沟学院 C++ 
只想搞钱的鸽子很喜欢...：混账是很多的，还有那些在自己风华正茂的年纪说风凉话讥讽那些下岗前员工的。这些人都是现在职场环境这么烂的帮凶 点赞 评论 收藏
分享