首页 > 其他 > 详细

【中位数推公式】 糖果传递

时间:2020-07-12 11:52:55      阅读:77      评论:0      收藏:0      [点我收藏+]

题意

传送门
\(N\)个人围成环形,每个人都有一定数量的糖果\(A_{i}\),每个人可以左右传递,
代价为\(1\),求让所有人的糖果数量相等所需要的最小操作数

数据范围

\(1\leq N \leq 10^{6}\)

题解

环形均分纸牌即选取某一个点,将环断开,进行均分纸牌的过程假设从第\(k\)个点出断开
那么变成了\(A_{k+1}, A_{k+ 2}, \ldots, A_{N}, A_{1}, \ldots, A_{k}\)
前缀和为\(S_{k+1}-S_{k}, S_{k+2}- S_{k}, \ldots, S_{M}-S_{k}, S_{1}+S_{M}-S_{k}, \ldots, S_{N}\)
其中\(S_{M}=0\)恒成立,所以就是求一个\(k\)使得\(\sum_{i=1}^{M}|S_{i}-S_{k}|\)最小
考虑方式同货仓选址,即中位数是最小操作

Code


【中位数推公式】 糖果传递

原文:https://www.cnblogs.com/hhyx/p/13287138.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!