bzoj 1045 糖果传递-白红宇

bzoj 1045 糖果传递

阅读量：5055 次

发布时间：2019-06-12

本文共 1276 字，大约阅读时间需要 4 分钟。

题目大意：

把noip均分纸牌变成了环

思路：

基本与均分纸牌相同

但是需要考虑的是起点的选择

首先我们可以设i个人开始有ai个糖

然后设第i个人给前一个人的糖果数为gi

则a[i]-g[i]+g[i+1]=avg；avg为最终每个人的糖果数即平均值

得到最终答案为所有abs(g[i])

设p数组表示a1+...+a[i]-i*avg 则

a[1]-g[1]+g[2]=avg→g[2]=avg-a[1]+g[1] =g[1]-p[1]

a[2]-g[2]+g[3]=avg→g[3]=avg-a[2]+g[2]=2avg-a[1]-a[2]+g[1]=g[1]-p[2]

以此类推

所以ans=abs(g[1])+abs(g[1]-p[1])+abs(g[1]-p[2])+...+abs(g[1]-p[n-1])

由于p数组是确定的

因此我们需要找到在数轴上到各个p数组的点距离最短的点

而这个数就是这些数的中位数

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #define ll long long 10 #define MAXN 1010101011 #define inf 2147483611 12 using namespace std; 13 ll read() 14 { 15 ll x=0,f=1; 16 char ch=getchar(); 17 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();} 18 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 19 return x*f; 20 }21 int a[MAXN],p[MAXN];22 ll ans,k,n,avg;23 int main()24 {25 n=read();26 for(int i=1;i<=n;i++) {a[i]=read();avg+=a[i];}27 avg/=n;28 for(int i=2;i<=n;i++) p[i]=p[i-1]-avg+a[i];29 sort(p+1,p+n+1);30 k=p[(n>>1)+1];31 for(int i=1;i<=n;i++) ans+=abs(k-p[i]);32 printf("%lld",ans);33 }