题面
第一反应断环为链, 转化为均分纸牌, 但复杂度为$latex O(N^2)$根本不对. 实际上这道题比均分纸牌只多了1与n之间的转移, 设 n给1 $latex x_n$个糖果, i给i+1 $latex x_i$个糖果, 则有:
$$\left\{ \begin{array}{ll}
a_1+x_n-x_1=av \\
a_2+x_1-x_2=av \\
a_i+x_{i-1}-x_i=av \\
\end{array} \right.$$
所以有
$$\left\{ \begin{array}{ll}
x_1=a_1+x_n-av=S_1+x_n-1*av \\
x_2=a_2+x_1-av=S_2+x_n-2*av \\
x_i=a_i+x_{i-1}-av=S_i+x_n-i*av \\
\end{array} \right.$$
答案为
$$\sum x_i=\sum_{i=1}^{n} |S_i +x_n- i*av|$$
这个式子表示数轴上的一系列点到点$latex -x_n$的距离值和, 根据几何意义可知$latex -x_n$为所有$latex S_i – i*av $中位数时总代价最小.
#include<cstdio>
#include<algorithm>
#define re register
#define in inline
#define int long long
using namespace std;
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b) return -s;
return s;
}
int n,s[1000010],d[1000010],av,mid,ans;
signed main()
{
n=read();
for(re int i=1;i<=n;++i) s[i]=read(),s[i]+=s[i-1];
av=s[n]/n;
for(re int i=1;i<=n;++i) d[i]=s[i]-i*av;
sort(d+1,d+n+1);
if(n&1) mid=d[n/2+1];
else mid=(d[n/2]+d[n/2+1])/2;
for(re int i=1;i<=n;++i) ans=ans+abs(d[i]-mid);
printf("%lld\n",ans);
return 0;
}
CGaZn的博客
最新评论