当前位置:首页 > 三分 > 正文
SSOJ2711糖果传递
68+

题目大意:n个小朋友围成一圈,分别有$a_i$​​ 颗糖果,现在每个人可以往左或者往右传递糖果,至少传递多少颗糖果才能让大家手上糖果数量一样?

题目描述

原题来自:HAOI 2008

有 n 个小朋友坐成一圈,每人有 $a_i$​​ 颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为 1 。求使所有人获得均等糖果的最小代价。

输入

第一行有一个整数 n ,表示小朋友个数;

在接下来 n 行中,每行一个整数 $a_i$。

输出

输出使所有人获得均等糖果的最小代价。

样例输入

4
1
2
5
4

样例输出

4

对于 30% 的数据,n≤1000;

对于 100 的数据,$n≤10​^6$​​,保证答案可以用 64 位有符号整数存储。

解题思路

均分纸牌加强版——有环!

容易想到破环成链:断开每个位置,贪心传糖果,时间复杂度$O(n^2)$,拿不到满分。另外一种想法就是只断开一个位置,那么如何让端口的位置不影响环的答案呢?该位置可以传递-s~s,枚举传递量即可。

如果传递x个糖果最好,那么传多了或者传少了都会导致答案增大!函数值是在[-s, s]是先递减再递增的,我们可以三分答案。

(推公式,转换成士兵站队问题也可以。)

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

SSOJ2711糖果传递:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter