网站建设公司在哪里找资源,普陀网站建设推广,网站可以用PS设计吗,北京商业网站建设题目描述 有\(n(n1000000)\)个小朋友坐成一圈#xff0c;每人有\(a_i\)个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为\(1\)#xff0c;求使所有人糖果数相等的最小代价。 暴力的做法比较显然#xff0c;有\(30\)分#xff0c;这里就不再赘述了。 推…题目描述 有\(n(n1000000)\)个小朋友坐成一圈每人有\(a_i\)个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为\(1\)求使所有人糖果数相等的最小代价。 暴力的做法比较显然有\(30\)分这里就不再赘述了。 推一波式子先考虑一条链的情况\(a[i]\)为原数组\(b[i]\)为\(a[i]\)每项分别减掉平均数的数组\(sum1[i],sum2[i]\)分别为\(a[i],b[i]\)的前缀和数组\(ave\)为平均数。则\(ans\)可表示为\(\sum\limits_{i1}^{n}|i*ave-sum1[i]|\)再化简得到\(\sum\limits_{i1}^{n}|sum2[i]|\)。然后是环形的情况断环为链的位置不同会变化的量就是前缀和数组。假设断环的位置为\(p\)则前缀和变为\(sum2[k1]-sum2[k],sum2[k2]-sum2[k]...\)减掉重复部分就是\(sum2[k]-sum2[1],sum2[k]-sum2[2]...\)所以答案就是\(\sum\limits_{i1}^{n}|sum2[k]-sum2[i]|\)结论就是\(sum2[k]\)为中位数时是最优的证明以后再补吧。照着式子写代码就好了。 #include cstdio
#include algorithmusing namespace std;#define N 1000000int n;
long long sum[N5], ave;int main() {scanf(%d, n);long long t, ans 0;for(int i 1; i n; i) scanf(%lld, t), ave t, sum[i] sum[i-1]t;ave / n;for(int i 1; i n; i) sum[i] - i*ave;nth_element(sum1, sum(n1)/2, sumn1);for(int i 1; i n; i) ans abs(sum[(n1)/2]-sum[i]);printf(%lld, ans);return 0;
} 转载于:https://www.cnblogs.com/dummyummy/p/9795849.html
