P2512 [HAOI2008]糖果传递

题目描述
有 n 个小朋友坐成一圈，每人有 \(a_i\)个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 1。

输入格式
小朋友个数 n，下面 n 行 \(a_i\)。

输出格式
求使所有人获得均等糖果的最小代价。

输入输出样例
输入
4
1
2
5
4
输出
4
说明/提示
\(n \leq 10^6\)

明天就要考试了(在一周考4次的前提下这句话好苍白)，打算写个蓝题给点信心，然后信心给了，给出去了，，

这个就是环形的均分纸牌问题。
一开始的时候想的是 \(ans = \displaystyle \sum_{i=1}^n |s[i] - i * ave|\)
然后就想换一个断点的影响，但是太难算了。结果看了题解才想起来这个要有一步\(a[i] = a[i] - ave\) 这样能简化运算。
那么\(ans = \displaystyle \sum_{i=1}^n |s[i]|\)然后就继续看题解，若以k为起点那么前缀和就成了
$s[k+1] - s[k] , s[k+2] - s[k] , \dots , s[n] + s[1] - s[k] , \dots , s[n] - s[k] + s[k] \( 然后提解说\)ans = \sum_{i=1}^n |s[i] - s[k]|$
于是我又卡住了，一直在想，这TM的是一个玩意么，，
后来才发现s[n] = 0我都快被自己蠢哭了。。。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
#define int long long
inline int read()
{
    register int x = 0 , f = 0; register char c = getchar();
    while(c < ‘0‘ || c > ‘9‘) f |= c == ‘-‘ , c = getchar();
    while(c >= ‘0‘ && c <= ‘9‘) x = (x << 3) + (x << 1) + c - ‘0‘ , c = getchar();
    return f ? -x : x;
}
int n;
int a[N] , s[N];
signed main()
{
	n = read(); int res = 0;
	for(int i = 1 ; i <= n ; ++i) res += (a[i] = read());
	res /= n;
	for(int i = 1 ; i <= n ; ++i) s[i] = s[i-1] + a[i] - res;
	sort(s + 1 , s + 1 + n);
	int tmp = s[(n + 1) >> 1] , ans = 0;
	for(int i = 1 ; i <= n ; ++i) ans += (tmp - s[i] > 0) ? (tmp - s[i]) : (s[i] - tmp);
	cout << ans << ‘\n‘;
	return 0;
}

P2512 [HAOI2008]糖果传递

原文：https://www.cnblogs.com/R-Q-R-Q/p/12770563.html