非常玄妙的一道题

一眼贪心？它可能和均分纸牌很像

我们考虑贪心，发现一脸不可做

设每个人手中的糖果数为 S_i ，平均值为 ave

假设每个人都给比自己标号小的人分糖果(第 1 个人给第 n 个人)，记为 X_i

则有 S_i - X_i + X_i-1 = ave

列好一个方程组，发现前 n - 1 个方程是可以表出第 n 个方程的，故舍去第 n 个式子

固定 X₁， 发现 X_i = (i - 1) * ave - ∑^i-1_j=1S_j + X_i

将其中的常数设为 -C_i

则有 C_i = ∑^i-1_j=1S_j - (i - 1) * ave

观察整个方程组发现答案变为 ∑ⁿ_i=1|X₁ - C_i|

看上去还是一脸不可做？

我们发现它的几何意义这时凸显了出来：在坐标轴上有 n 个点 C₁, C₂, C₃, ... , C_n，求使得 X₁ 到各点的距离和最小的 X₁ 的值

那么这个问题突然就变得一脸可做了起来

n 为偶数时，X₁ ∈ [C_n/2, C_(n/2)+1]

n 为奇数时，X₁ = C_n/2

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std; const int MAXN = 1000001; typedef long long ll; int n;ll num[MAXN], c[MAXN]; int main() { scanf("%d", &n); ll ave = 0; for(int i = 1; i <= n; ++i) scanf("%lld", &num[i]), ave += num[i]; ave /= n; for(int i = 1; i <= n; ++i) c[i] = c[i - 1] + num[i] - ave; sort(c, c + n); ll pos = c[(n / 2)]; ll ans = 0; for(int i = 0; i < n; ++i) ans += abs(pos - c[i]); printf("%lld\n", ans); return 0;}