M_sea

洛谷2512 [HAOI2008]糖果传递
Luogu分析提示:排序/中位数/环形均分纸牌不过均分纸牌变成环后就从橙题到蓝题了qwq尝试手推一遍过程。首先,要...
扫描右侧二维码阅读全文
29
2018/11

洛谷2512 [HAOI2008]糖果传递

Luogu

分析

提示:排序/中位数/环形均分纸牌

不过均分纸牌变成环后就从橙题到蓝题了qwq


尝试手推一遍过程。

首先,要让每个孩子的糖果数都变为

$$\Large\overline{a}=\frac{\sum\limits_{i=1}^{n}a_i}{n}$$

和均分纸牌一样,设$x_i$表示给上一个人的糖果数,正数就是给,负数就是拿。

这里传给编号大的人后面会不好推,所以选择传给编号小的那个人。

然后传递后第$i$个人的糖果数$b_i$就是:

$$\Large b_i=a_i+x_{next}-x_{i}$$

显然$\forall b_i,b_i=\overline{a}$。

然后就可以列方程组:

$$\Large\begin{cases}a_1+x_2-x_1=\overline{a}\\a_2+x_3-x_2=\overline{a}\\......\\a_n+x_{1}-x_n=\overline{a}\end{cases}$$

发现这个方程组解不出,所以用$x_1$来表示$x_i(i\neq 1)$。

容易得到:

$$\Large\begin{cases}x_2=\overline{a}-a_1+x_1\\x_3=\overline{a}-a_2+x_2\\......\\x_{n}=\overline{a}-a_{n-1}+x_{n-1}\end{cases}$$

然后再化简,得到:

$$\Large x_i=x_1+\sum\limits_{j=1}^{i-1}\ \overline{a}-a_j\quad(2\leq i\leq n)$$

定义:

$$\Large c_i=\begin{cases}0&i=1\\\sum\limits_{j=1}^{i-1}\ a_j-\overline{a}&2\leq i \leq n\end{cases}$$

然后就变成了:

$$\Large x_i=x_1-c_{i}$$

试着写出答案:

$$\Large ans=\sum\limits_{i=1}^{n}\ |x_i|\Rightarrow ans=\sum\limits_{i=1}^{n}\ |x_1-c_i|$$

我们要取一个$x_1$,使得$ans$最小。易证$x_1$取$c_m\ (m=\left\lceil \frac{n}{2} \right\rceil)$时$ans$最小。

具体实现见代码。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1e6+10;

int n,ave=0;
int a[MAXN],c[MAXN];

mainint main() {
    n=read();
    for (re int i=1;i<=n;++i) ave+=(a[i]=read());
    ave/=n;
    for (re int i=2;i<=n;++i) c[i]=c[i-1]+ave-a[i];
    stable_sort(c+1,c+n+1);
    int mid=c[(n+1)>>1],ans=0;
    for (re int i=1;i<=n;++i) ans+=abs(mid-c[i]);
    printf("%lld\n",ans);
    return 0;
}
最后修改:2018 年 12 月 02 日 09 : 24 PM

发表评论