From The Stupid
Bad at Coding
BZOJ 1045: [HAOI2008] 糖果传递
starli
posted @ 2016年2月08日 17:02
in 乱搞？
, 428 阅读
设第i个小朋友从左边拿bi个 平均数为t
ai+bi-b(i+1)=t 不妨设b1=k
则 bn = k+t-an
bn-1 = k+2t-an-a(n-1)
bn-2 = k+3t-an-a(n-1)-a(n-2)
...
费用为sum(|bi|) 似乎3分就可以了？
不 还可以更快 绝对值的式子怎么化简呢？
考虑数形结合 那么就转化成了：k到各个数字的距离 于是就是中位数了！
然而这个复杂度还是nlogn的……
这道题好像刘汝佳的训练指南上第一章有讲到过，也可以参考那个的解答
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1000010;
LL n,a[N],t,tmp[N],k,ans;
void read(LL &x){char c;while((c=getchar())<'0'||c>'9');x=c-'0';while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';}
int main(){
//freopen("1045.in","r",stdin);freopen("1045.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
t=a[n]/n;
tmp[n]=0;
for(int i=1;i<n;i++) tmp[i]=i*t-a[n]+a[n-i];
std::sort(tmp+1,tmp+n+1);
k=tmp[(n+1)>>1];
for(int i=1;i<=n;i++) ans+=abs(k-tmp[i]);
printf("%lld",ans);
return 0;
}
评论 (0)