acgo题库
  • 首页
  • 题库
  • 学习
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情提交记录(0)
  • A21578.负载平衡问题 题解

    其实这题和A118挺像的,只不过那题是一条链,而这题是一个环,但是思想都一样,都是用平均数来做文章。 想象一堆牌围成一圈,在脑中模拟分牌过程,你会发现一个性质:必定至少有两堆相邻的牌不需要从别的纸牌堆那里获得纸牌。 于是,我们可以利用这个性质,把环破坏成链,枚举不需要交换纸牌的那两堆纸牌,将其分别放在链的第一个位置与最后一个位置。 最后按开始的序列顺序,像普通均分纸牌一样预处理出 bbb 数组。设枚举的位置为 kkk,平均数为 sumsumsum,bib_ibi 设为 ai−suma_i-sumai −sum 的前缀和,则题目就是求 ans=∑∣bk−bi∣ans=\sum \left|b_k-b_i\right|ans=∑∣bk −bi ∣ 的最小值了。根据初中的知识可得当 kkk 为 n+12\frac{n+1}{2}2n+1 时 ansansans 的值最小。 建议将为普及- 或者 普及/提高-,这题并不难。

    userId_undefined

    jcf666

    秩序白银
    15阅读
    3回复
    1点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页