题解"/>
糖果传递题解
前言
原题戳这里
题目
题目描述
有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
输入输出格式
输入格式:
小朋友个数n 下面n行 ai
输出格式:
求使所有人获得均等糖果的最小代价。
输入输出样例
输入样例#1:
4
0 1
0 -1
1 0
-1 0
输出样例#1:
4
数据范围
对于100%的数据 n≤106 n ≤ 10 6
解法
显然觉的这道题有很多值得深入挖掘的性质,比如每个人最终的状态求个平均值就好了
那么先不考虑算法,而是研究一波题面。
显然,代价的计算是一个麻烦的事情。我们认为代价的计算应该是与路径有关,而不是与人有关。也就是说,我们关心的是两个人之间的路径上糖果移动的情况。
我们又发现,一条路径上糖果的移动方向只有一个,可以用正负来表示。接着我们还发现,只要知道了一条路径上糖果的移动情况,那么其他路径也是可以推出来的。
这时,暴力已经出来了,也就是暴力枚举每一条路径的糖果运送情况,最后把结果求min就可以了。
但越深入的思维越接近题目的本质。到了这里就不妨把这个式子推一下。
发现最终长这样
设w为第一个小朋友与最后一个小朋友的路径上的情况,x为平均值,ai为第i个小朋友的糖果,显然代价p有
这样就是一个小学奥数。用绝对值的几何意义求一下就可以了。由于没有用到任何算法,复杂度随意
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T>
inline void read(T&data){register char ch=0;data=0;while(ch<'0'||ch>'9')ch=getchar();while(ch<='9'&&ch>='0'){data=(data<<3)+(data<<1)+(ch^48);ch=getchar();}
}
const int _ =1e6+5;
LL n,a[_],s[_];
bool cmp(register LL x,register LL b){return x<b;}
int main(){//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);read(n);LL x=0;for(register int i=1;i<=n;++i)read(a[i]),x+=a[i];x/=n;LL df=x;s[1]=a[1]-x;register LL now=a[1];for(register int i=2;i<=n;++i){now+=a[i];x+=df;s[i]=now-x;}sort(s+1,s+n+1,cmp);register LL ans=0;for(register int head=1,wei=n;head<=wei;head++,wei--){ans+=(s[wei]-s[head]);}cout<<ans;
}
更多推荐
糖果传递题解
发布评论