1045: [HAOI2008] 糖果傳遞
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2975 Solved: 1327
[Submit][Status][Discuss]

Description
有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個糖果代價為1。

Input
小朋友個數n 下面n行 ai

Output
求使所有人獲得均等糖果的最小代價。

Sample Input
4
1
2
5
4

Sample Output
4

HINT
100% n<=987654321
（這個數據范圍加了特技，真實范圍n<=1000000,Duang）

數學題，可以說是**均分紙牌**的環狀問題 首先數組get【i】表示第i個小朋友從第i+1個小朋友那里得到的糖果，可正可負 所以也可以表示第i+1個小朋友給第i個小朋友的糖果，即第i+1個小朋友失去的數量

所以我們不難得出：
candy【i】+get【i】-get【i-1】=pj（平均）
這一步并不足以求解
所以移項可得：
get【i】=pj-candy【i】+get【i-1】
上述式子可以推出get的值，那么問題在于從哪里開始最小
問題為圓環，最小想到距離，距離想到中位！！
于是…..A之

代碼精煉至極：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std;#define maxn 1000002 long long candy[maxn]={0}; long long get[maxn]={0};int main() {int n;long long sum=0,pj=0;long long ans=0;scanf("%d",&n);for (long long i=1; i<=n; i++){scanf("%d",&candy[i]);sum+=candy[i];}pj=sum/n;for (long long i=1; i<=n; i++)get[i]=get[i-1]+pj-candy[i];sort(get+1,get+n+1);long long mid=get[(1+n)/2];for (long long i=1; i<=n; i++)ans+=fabs(mid-get[i]); printf("%lld",ans);return 0; }

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5346249.html

總結

以上是生活随笔為你收集整理的BZOJ-1045 糖果传递 数学+递推的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。