牛客IOI周赛23-提高组C.星星-环形纸牌问题

链接：https://ac.nowcoder.com/acm/contest/11165/C

题目描述

牛牛带着他的小伙伴跑去天上摘星星了。 每一只牛都摘了一堆星星，由于他们去的区域不同，所以所摘的星星数量也不同，但是他们是相亲相爱的一家人，所以他们围成一个圈（按顺序编号1到n，第i只牛牛有ai颗星星），他们想办法将星星数量均分，但是牛牛们的手很短，每次只能跟相邻的一个人进行交易， 在问最少需要交易多少次，每个人才能获得相等的星星，题目保证有解。

输入描述:

第一行一个正整数n，表示有多少只牛牛
第二行n个非负整数 a1,a2,...,an，表示每只牛牛摘了多少颗星星

输出描述:

一行一个正整数表示最少需要交易多少次才能使得每只牛牛获得相等的星星

示例1

输入

4
0 2 8 6

输出

8

说明

4给1两个，3给2四个，2给1两个，2+4+2=8

备注:

对于10%的数据，满足n≤2
对于30%的数据，满足n≤200
对于60%的数据，满足n≤2000
对于80%的数据，满足n≤100000
对于100%的数据，满足1≤n≤1000000，0≤ai≤1e9

题目分析

本题目重在考查问题的转化思想和贪心算法。

一圈牛拥有各自的星星，位置固定，要求互传使每个牛的星星数相等。

一圈牛相邻能传看起来不好处理，但是我们可以规定一个传递方向：单向传，但是能传递负数个星星。

首先，我们设置数组 a a a储存每头牛手上的星星，同时求和并得出平均值 a v e ave ave；同时我们设置数组 c c c表示当前牛 i i i向左 ( i − 1 ) (i -1) (i−1)传递的星星，注意首元素 c [ 1 ] c[1] c[1]表示向末尾元素 c [ n ] c[n] c[n]传递的星星数(满足题目围成一圈的需求)。

那么最终的答案可以表示为 ∣ c 1 ∣ + ∣ c 2 ∣ + ∣ c 3 ∣ + . . . + ∣ c n ∣ = ∑ i = 1 n ( c [ i ] ) |c_1| + |c_2| + |c_3| + ... + |c_n| = \sum ^{n} _{i = 1}(c[i]) ∣c1​∣+∣c2​∣+∣c3​∣+...+∣cn​∣=∑i=1n​(c[i])

理想状态 a v e ave ave是每头牛最后应该拥有的星星数，我们对式子进行分析：

对第一头牛： a 1 + c 2 − c 1 = a v e a_1 + c_2 - c_ 1 = ave a1​+c2​−c1​=ave

对第二头牛： a 2 + c 3 − c 2 = a v e a_2 + c_3 - c_2 = ave a2​+c3​−c2​=ave

…

对第 n n n头牛： a n + c 1 − c n = a v e a_n + c_1 - c_n = ave an​+c1​−cn​=ave

对各式移项并展开，可得：

c 2 = c 1 − ( a 1 − a v e ) c_2 = c_1 -(a_1- ave) c2​=c1​−(a1​−ave)

c 3 = c 2 − ( a 2 − a v e ) = c 1 − ( a 1 + a 2 − 2 ∗ a v e ) c_3 = c_2 - (a_2 - ave) = c_1 - (a_1 + a_2 - 2 * ave) c3​=c2​−(a2​−ave)=c1​−(a1​+a2​−2∗ave)

…

c n = c n − 1 − ( a n − 1 − a v e ) = c 1 − ( ∑ i = 1 n − 1 a [ i ] − ( n − 1 ) ∗ a v e ) c_n = c_{n - 1} - (a_{n - 1} - ave) = c_1 - (\sum^{n - 1} _{i = 1}a[i] - (n - 1) * ave) cn​=cn−1​−(an−1​−ave)=c1​−(∑i=1n−1​a[i]−(n−1)∗ave)

观察上述式子，我们将与 c c c无关的项提取出来：设 t 1 = a 1 − a v e ,   t 2 = t 1 + a 2 − a v e ,   . . .   ,   t i = t i − 1 + a i − a v e t_1 = a_1 - ave, \ t_2 = t_1 + a_2 - ave, \ ...\ ,\ t_i = t_{i - 1} + a_i - ave t1​=a1​−ave, t2​=t1​+a2​−ave, ... , ti​=ti−1​+ai​−ave 则答案转化为 m i n ( ∣ c 1 − t 1 ∣ + ∣ c 1 − t 2 ∣ + . . . + ∣ c 1 − t n − 1 ∣ ) min(|c_1 - t _1| + |c_1- t_2|+ ... + |c_1 - t_{n - 1}|) min(∣c1​−t1​∣+∣c1​−t2​∣+...+∣c1​−tn−1​∣)，此时题目被转换成了贪心问题：数轴上有 n n n个点，找出某个到他们距离之和最小的点。我们只需要将数组排序，取中位数进行计算即可得到最小值。

AC CODE:

#include 
#define ll long long
using namespace std;
long long a[1000001], c[1000001];
int main() {
    ios_base::sync_with_stdio(0);
    ll n, ans = 0, ave = 0; cin >> n;
    for (int i = 0; i > a[i];
        ave += a[i];
    }
    ave /= n;
    for (int i = 0; i