BZOJ1045 [HAOI2008] 糖果传递

题意

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

题解

​ 设xi表示 $i$给$i-1$的糖果数,$xi$可以是负数。

​ 得到平均数$ave$

​ $a1 - x1 + x2 = ave$
​ $a2 - x2 + x3 = ave$
​ ……
​ $an - xn + x1 = ave$

转化一下
​ $x2 - x1 = ave - a1$①
​ $x3 - x2 = ave - a2$②
​ $x4 - x3 = ave - a3$③
​ ……
我们把①和②加起来得到
​ $x3 - x1 = 2 * ave - a1 - a2$
同理
​ $x4 - x1 = 3 * ave - a1 - a2 - a3$
​ ……
​ 设$si = i * ave - a1 - a2 - a3 - …… - ai $
其中s0 = 0

​ $x1 = x1 + s0$
​ $x2 = x1 + s1$
​ $x3 = x1 + s2$
……
要的是最小化
​ $|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. 题解
|