| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴个代码 排序后O(n)#include <iostream>
#include <algorithm>
using namespace std;
namespace p2231{
const int M = 10002;
int pos[M];
};
using namespace p2231;
int main(void){
int n;
cin>>n;
for(int i=0;i<n;i++)
scanf("%d",&pos[i]);
sort(pos,pos+n); //排序后才能用质心的思路
long long sum,a1,a2,total;
sum = total = 0;
for(int i=0;i<n-1;i++){
a1 = pos[i];
a2 = pos[i+1];
total += a1; // total/(i+1)可以认为是质心
sum += (a2*(i+1)-total)<<1;
}
printf("%I64d\n",sum);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator