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