[集训Day1]糖果传递[HAOI2008](贪心)

题目描述

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

Input
第一行一个正整数n<=1000000,表示小朋友的个数.

接下来n行,每行一个整数ai,表示第i个小朋友得到的糖果的颗数.

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

Sample Input
4
1
2
5
4

Sample Output
4

对于30%30 \%的数据,n1000n \leq 1000
对于100%100 \%的数据,n106n \leq 10^6,保证答案可以用64位有符号整数存储。

题目解析

数学方式求解:

由题易得avg=Σi=1nai÷navg = \Sigma_{i=1}^n a_i \div n
从而假设,第ii个人从第i1i-1个人手里拿到xix_i个糖果,传递给第i+1i+1个人xi+1x_{i+1}个糖果后达到了avgavg
    avg=ai+xixi+1avg=a1+x1x2avg=a2+x2x3avg=a3+x3x3avg=an+xnx1\implies avg = a_i + x_i - x_{i+1}\\ \therefore avg = a_1 + x_1 - x_2\\ avg = a_2 + x_2 - x_3\\ avg = a_3 + x_3 - x_3\\ ……\\ avg = a_n + x_n - x_1\\
    x2=a1avg+x1x3=a2avg+x2=(a1+a2)2×avg+x1x4=a3avg+x3=(a1+a2+a3)3×avg+x1    xn=Σi=1n1ai(n1)×avg+x1=Σi=1n1[aiavg]+x1 \implies x_2 = a_1 - avg + x_1\\ x_3 = a_2 - avg + x_2= (a_1+a_2) - 2\times avg + x_1\\ x_4 = a_3 - avg + x_3= (a_1+a_2+a_3) - 3\times avg + x_1\\ ……\\ \implies x_n = \Sigma_{i=1}^{n-1} a_i - (n-1)\times avg + x_1 = \Sigma_{i=1}^{n-1} [a_i - avg] + x_1

故最后求得通项

xn=Σi=1n1[aiavg]+x1\Large x_n = \Sigma_{i=1}^{n-1} [a_i - avg] + x_1

Ci=Σi=1n1[avgai]C_i = \Sigma_{i=1}^{n-1} [avg - a_i]
xn=x1Ci    x1=x1C0;x2=x1C1;x3=x1C2;xn=x1Cn1;\therefore x_n = x_1 - C_i\\ \implies x_1 = x_1 - C_0;\\ x_2 = x_1 - C_1;\\ x_3 = x_1 - C_2;\\ ……\\ x_n = x_1 - C_{n-1};\\
此时,问题为求min(Σi=1nxi)min(\Sigma_{i=1}^n x_i),则通过以上步骤我们将问题转化成为了x1x_1到数列CiC_i各项的距离之和的最小值。也就是求数列CiC_i的中位数到数列各项的距离之和。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll a[1000002],c[1000002] = {0};
int main() {
ll n = 0,avg = 0;
scanf("%ld",&n);

for (ll i = 1; i <= n; i++){
cin>>a[i];
avg += a[i];
}
avg /= n;


for (ll i = 1; i < n; i++)
c[i] = (avg - a[i])+c[i-1];
sort(c,c+n);

ll ans=0,midle;
if(n&1){
midle=c[n/2];
}
else{
midle=(c[(n-1)/2]+c[(n-1)/2+1])/2;
}

for(ll i=0;i<n;i++){
ans+=abs(c[i]-midle);
}
cout<<ans<<endl;
return 0;
}
文章作者: Tim
文章链接: http://itstim.xyz/%E9%9B%86%E8%AE%ADDay1-%E7%B3%96%E6%9E%9C%E4%BC%A0%E9%80%92-HAOI2008-%E8%B4%AA%E5%BF%83/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tim's Blog
支付宝恰饭打赏
微信恰饭打赏