UVA11300

初步解題原理:代數運算+單元素極值

代數運算:

xi表示第i個給i-1的數量，正負表示給或得

c=(a1+a2+a3....an)/n

a1-x1+x2=c -->x2=x1-a1+c

a2-x2+x3=c -->x3=x1-a1-a2+2c

a3-x3+x4=c -->x4=x1-a1-a2-a3+3c

......

an-xn+x1=c -->xn=x1-a1-a2-a3....-a(n-1)+(n-1)c

ans=max{|x1|+|x2|+|x3|+....|xn|=|x1-0|+|x1-a1+c|+|x1-a1-a2+2c|.......|x1-a1-a2-a3....-a(n-1)+(n-1)c|}

我們可以用x1表示任意量

ans=min{|x-b1|+|x-b2|+|x-b3|+|x-b4|.......+|x-bn|}

當x取{b1,b2,b3,.....bn}排序后的中位數時，ans取最小值

 1 #include<iostream>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 #include<stdio.h>
 6 #define ULL unsigned long long
 7 #define LL long long
 8 #define maxn 1000009
 9 using namespace std;
10 LL a[maxn];
11 LL b[maxn];
12 int main()
13 {
14     int n;
15     while(~scanf("%d",&n))
16     {
17         ULL C=0;
18         for(int i=1;i<=n;i++)
19         {
20             scanf("%lld",&a[i]);
21             C+=a[i];
22         }
23         C=C/n;
24         b[0]=0;
25         for(int i=1;i<n;i++)
26         {
27             b[i]=b[i-1]-C+a[i];
28         }
29         sort(b,b+n);
30         ULL ans=0;
31         LL mid=b[n/2];
32         for(int i=0;i<n;i++)
33         {
34             ans+=abs(mid-b[i]);
35         }
36         printf("%lld\n",ans);
37     }
38     return 0;
39 }

轉載于:https://www.cnblogs.com/little-w/p/3341947.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/274004.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/274004.shtml
英文地址，請注明出處：http://en.pswp.cn/news/274004.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！