P2512 [HAOI2008]糖果传递

题目描述

有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

输入输出格式

输入格式：

小朋友个数n 下面n行 ai

输出格式：

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

---

错误日志： 数据范围没给出于是只用了int

---

Solution

环形纸牌均分

首先想到环上的某两个相邻点一定没有发生过交换（因为最后的那个人不需要再把牌给谁了， 前面每个人都分好了， 自己肯定也是好的）

所以最先想到的是枚举那一个不交换的断点， 拆成链做纸牌均分， 复杂度 \(O(n^{2})\) ， 显然不能承受

于是我们先按常规每个点减去平均数， 试着列举有断点的情况下的数据（\(A[i]\) 表示这个点减去平均数后有多少牌， \(Sum[i]\) 表示其前缀和）

以 \(k\) 后面为断点（断点处于 \(k\) 和 \(k +1\) 之间）时， 有：

\(A[k + 1]\ \ \ \ \ \ \ \ Sum[k +1] - Sum[k]\)

\(A[k + 2]\ \ \ \ \ \ \ \ Sum[k +2] - Sum[k]\)

\(A[k + 3]\ \ \ \ \ \ \ \ Sum[k +3] - Sum[k]\)

\(......\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ......\)

\(A[n]\ \ \ \ \ \ \ \ Sum[n] - Sum[k]\)

\(A[1]\ \ \ \ \ \ \ \ Sum[1] + Sum[n] - sum[k]\)

\(A[2]\ \ \ \ \ \ \ \ Sum[2] + Sum[n] - sum[k]\)

\(......\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ......\)

\(A[k]\ \ \ \ \ \ \ \ Sum[k] + Sum[n] - sum[k]\)

于是发现一个问题： \(Sum[n] = 0\) ！为什么呢？ 他是最后一张牌， 到这里前缀和当然为 \(0\) !

也就是说， 在 \(k\) 处断开时， 前缀和数组的变化为 \(-= sum[k]\)

于是答案可以写成这个\[\sum_{i = 1}^{n}\left|Sum[i] - Sum[k]\right|\]

显然当 \(Sum[k]\) 为中位数时， 答案最小

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          typedef long long LL;using namespace std;LL RD(){ LL out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const LL maxn = 1000019;LL num, ave;LL a[maxn], sum[maxn];int main(){ num = RD(); for(LL i = 1;i <= num;i++)a[i] = RD(), ave += a[i]; ave /= num; for(LL i = 1;i <= num;i++)a[i] -= ave, sum[i] = sum[i - 1] + a[i]; sort(sum + 1, sum + 1 + num); LL mid = sum[num >> 1], ans = 0; for(LL i = 1;i <= num;i++)ans += abs(sum[i] - mid); printf("%lld\n", ans); return 0; }