题解 | #带权中位数#

带权中位数

https://ac.nowcoder.com/acm/problem/284613

笔记


解法一:

  • 结论人数刚刚过半的那个点就是目标点
  • 证明:

alt

  • 实现:统计每个点的人数,然后对其求前缀和

解法二:

先求出所有人到一号点的总路程,然后计算目标点从1变成2的时候的总路程的变化量来计算目标点为2时的总路程。

dist(x+1) = dist(x) + (Px+1 - Px) * (x及其之前的人数 - x+1及其之后的人数)

全部评论

相关推荐

2025-12-30 16:42
同济大学 C++
仁狂躁使者:哎呀,不用担心,我当时配环境配了两天,项目捋不清就问问导师能不能用ai,慢慢就清了,会好起来的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务