poj 2231

题意：给出 n 头牛，给出 n 头牛的位置，求出每头牛到其他牛的距离的总和

按给的牛的位置从小到大排序，假设第 i 头牛的位置为 xi ，那么它前面的牛的个数假设是 N 个，并且我们可以求出它前面这些牛的 x （位置）值的和记为 sum，那么它前面的这些牛到他的距离就是 N * xi - sum，同样处理它后面的那些牛的距离，对每头牛都这样处理后，把每头牛到其他牛的距离总和相加，就是答案

代码写的有点乱

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<string>
 6 #include<vector>
 7 //#include<map>
 8 #include<queue>
 9 #include<stack>
10 #include<cmath>
11 #include<set>
12 #define N 10001
13 #define inf 100000000
14 #define _clr(a,val) (a,val,sizeof(a))
15 #define Min(x, y)   x < y ? x : y
16 #define Max(x, y)   x < y ? y : x
17 
18 using namespace std;
19 
20 typedef long long ll;
21 
22 struct node
23 {
24     ll id,x;
25 }a[N];
26 bool cmp(node a,node b)
27 {
28     return a.id < b.id;
29 }
30 ll sum [N];
31 ll sumx[N];
32 int main()
33 {
34     ll n,i,j;
35     while(cin>>n)
36     {
37         for(i = 1; i <= n; i++)
38         {
39             cin>>a[i].id;
40         }
41         sort(a + 1,a + n + 1,cmp);
42         _clr(sum,0);
43         _clr(sumx,0);
44         for(i = 1; i <= n; i++)
45         sum[i] = sum[i - 1] + a[i].id;
46         for(i = 1; i <= n; i++)
47         {
48             sumx[i] = (((i - 1) * a[i].id - sum[i - 1]) + ((sum[n] - sum[i]) - (n - i) * a[i].id));
49         }
50         ll tsum = 0;
51         for(i = 1; i <= n; i++)
52         tsum += sumx[i];
53         cout<<tsum<<endl;
54     }
55     return 0;
56 }