Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个代码 排序后O(n)

Posted by mandycool at 2012-07-03 11:41:33 on Problem 2231
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator