poj-2231(Moo Volume) 递推

题意：给你n个数求n个数任意一个数与其他数之差的绝对值之和的和

题解：例如；

6

1 2 5 7 8 9

先排序

正向：

1 --->9                                  8

1 --->2----->9                        8

1 --->5----->9                        8

1 --->7----->9                        8

1 --->8----->9                         8

2 --->8                                  6

2 --->5----->8                        6

2 --->7----->8                        6

5--->7                                   2

sum   =  8 *  5 + 6 * 3  + 2 * 1；

逆向同上述方法

 sum的值相同；

  

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long LL; LL a[10005]; int main() {LL n,i,j;while(~scanf("%lld",&n)){for(i = 0;i < n;i++)scanf("%lld",&a[i]);sort(a,a+n);i = 0;j = n - 1;LL sum = 0;while(i < j){sum += (a[j] - a[i]) *(j - i);i++,j--;}printf("%lld\n",2*sum);} }
                 

总结

以上是生活随笔为你收集整理的poj-2231(Moo Volume) 递推的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。