注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1045】【HAOI2008】【糖果传递】  

2014-03-10 21:33:41|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   如果是链的话就是均分纸牌,如果再改一下条件就有点像长城守卫...感觉模型都很类似的感觉....
   先来看看均分纸牌怎么做,咱们先求平均数,求出每一份纸牌的需求量,然后从左往右取,为什么可以贪心?因为左边的链的纸牌一定是从它相邻右边那个来的,而它多余的纸牌也一定是给右边的,所以直接取就可以了。那么这个就不行了。这个是环形的,咱们假设咱们拆成链的话,那么还有一种可能就是最左边给了最右边一些纸牌,这样贪心不成立。但是咱们也可以做,咱们可以假设一口气给了右边K张之后就不再给(假设分多次给的话不如一次给),这样就强行拆成链状了。那么关键是求多少个K为好。
   对于均分纸牌,设i堆给右边p[i]张纸牌,设每一堆纸牌为a[i],则总的操作数为∑p[i],然后咱们又有递推式
a[i]+p[i-1]-ave=p[i].则∑abs(p[i]) 就是答案。
  这里展开下不难发现 p[i]=∑a[j] - j*ave
  然后就是 环状,环可以拆成链,但是它不满足贪心的性质,可是咱们可以让他满足,咱们之前假设了从头到末一次性给了K张,且之后不再给了,那么它就变成了均分纸牌了(假设分别给两次显然还不如直接给)
  那么 咱们的 a[1]=a[1]-k,则 p[1]=p[1]-k,则p[2]=p[2]-k,p[3]=p[3]-k......而a[n]=a[n]+k,p[n-1]=p[n-1]-k。即所有的p[]都变小了。
  即 ∑abs(p[i]-k)最小,显然这货就是p的中位数最好。 
=================================

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define maxn 1000010
using namespace std;

int n,a[maxn],p[maxn];
long long sum=0;

int main()
{
    int i;
    scanf("%d",&n);
    memset(p,0,sizeof(p));
    for (i=0;i<n;i++) scanf("%d",&a[i]),sum+=a[i];
    sum=sum/n;
    for (i=0;i<n;i++) a[i]-=sum,p[i]=i==0?a[i]:p[i-1]+a[i];
    sort(p,p+n);
    for (i=0,sum=0;i<n;i++) sum+=abs(p[i]-p[n>>1]);
    printf("%lld",sum);
    system("pause");
    return 0;
}


   
  评论这张
 
阅读(46)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017