BZOJ1045 [HAOI2008] 糖果传递

题意

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

题解

​ 设xi表示 iii1i-1的糖果数,xixi可以是负数。

​ 得到平均数aveave

a1x1+x2=avea1 - x1 + x2 = ave
a2x2+x3=avea2 - x2 + x3 = ave
​ ……
anxn+x1=avean - xn + x1 = ave

转化一下
x2x1=avea1x2 - x1 = ave - a1
x3x2=avea2x3 - x2 = ave - a2
x4x3=avea3x4 - x3 = ave - a3
​ ……
我们把①和②加起来得到
x3x1=2avea1a2x3 - x1 = 2 * ave - a1 - a2
同理
x4x1=3avea1a2a3x4 - x1 = 3 * ave - a1 - a2 - a3
​ ……
​ 设$si = i * ave - a1 - a2 - a3 - …… - ai $
其中s0 = 0

x1=x1+s0x1 = x1 + s0
x2=x1+s1x2 = x1 + s1
x3=x1+s2x3 = x1 + s2
……
要的是最小化
x1+x2+x3|x1| + |x2| + |x3|……
也就是最小化
​ $|x1 - (-s1)| + |x2 - (-s2)| …… …… ​ 令x1 = -s1,-s2,-s3……$的中位数。
然后算出来就行了

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
namespace IO{
#define getch getchar
LL read(){LL T = 0,f = 1;char c = getch();while ((c<'0'||c>'9')&&c!='-') c=getch();if(c=='-')f=-1,c=getch();while (c>='0'&&c<='9'){T=((T<<1)+(T<<3))+c-48;c=getch();}return T*f;}
inline void write(LL x){if(x < 0) putchar('0'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
};
#define pc putchar
using namespace IO;
LL s[1000005],a[1000005],x1,n,sum,ave,Ans;
int main(){
n = read();
for (int i=1;i<=n;i++) a[i] = read(),sum+=a[i];
ave = sum / n;
s[0] = 0;
for (int i=1;i<n;i++)
s[i] = s[i-1] + ave - a[i];
for (int i=0;i<n;i++) s[i]=-s[i];
sort(s,s+n);
x1 = s[n>>1];
Ans = 0;
for (int i=0;i<n;i++) Ans += abs(x1 - s[i]);
write(Ans);pc('\n');
return 0;
}
文章目录
  1. 1. 题意
  2. 2. 题解