采票网站刷流水做任务,网站建设方案及预算,上海奉贤做网站,wordpress如何发照片题意 有n个小朋友坐成一圈#xff0c;每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 思路 假设平均数是x#xff0c;且a1给an了k个#xff08;k0说明是an给a1了-k个#xff09;#xff0c;那么总代价就可以算出来#xff1a; ananka1-…题意 有n个小朋友坐成一圈每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 思路 假设平均数是x且a1给an了k个k0说明是an给a1了-k个那么总代价就可以算出来 ananka1-ka2代价|k|xa1a2-x-ka3代价|a1-x-k|xa1a2a3-2x-k代价|a1a2-2x-k|x代价|a1a2a3-3x-k| 令bisum(a1..i)-ix则总代价sum|bi-k|。易知k为中位数时此值最小。问题转化为求中位数…… 用自己快速选择第K大模板TLE……sort直接过了…… 代码 [cpp] #include iostream #include cstdio #include cmath #include algorithm #include string #include cstring #include vector #include set #include stack #include queue #define MID(x,y) ((xy)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, end) for (int i begin; i end; i ) using namespace std; const int maxn 1000005; int a[maxn]; long long sum[maxn], b[maxn]; int main(){ int n; scanf(%d, n); sum[0] 0; REP(i, 1, n){ scanf(%d, a[i]); sum[i] sum[i-1] a[i]; } long long average sum[n] / n; REP(i, 0, n-1){ b[i] sum[i] - (i) * average; } sort(b, bn); long long res 0; REP(i, 0, n-1){ res abs(b[i] - b[n/2]); } printf(%lld\n, res); return 0; } [/cpp]转载于:https://www.cnblogs.com/AbandonZHANG/p/4114124.html
