题解： 将问题转变为：在一个长度为10000000的圆上有n（2<=n<=100000）个点,每个点都有一个坐标值表示该点所在的位置，求一个点，使得该点到其他所有点的距离之和最小，求出该最小值。

首先想到的是遍历这1千万个点，对于每一个点求其他点到该点的距离和，然后选择之1千万个距离和中的最小值作为结果。需要计算1千万的平方次，超时，不可行！容易发现并不需要计算这1千万个点，因为其中很多点的计算结果是一样的。其实只需要计算n次就行了，对于每个点计算其他点到该点的距离和。计算复杂度为O(n2)，因为n最大为10万，用这种方法提交也出现超时。观察后发现，基点从i-1变成i时，并不需要重新计算i点到所有其他点之间的距离，只需要修改一些改变了的距离就可以。用D[i]表示以i点为基点的距离和。

首先将n个点按位置大小排序，遍历选择n个点作为基点计算距离和。例如：选择0点作为基点，计算其对称点s=(P[0]+1000000/2)%1000000，则以0点为基点的距离和D[0]为其他各点到0点的距离之和，1、2、3点计算逆时针到0点的距离，4、5、6计算顺时针到0点的距离。

算法描述

（1）将输入n个数据按从小到大排序。为了计算方便，将n个数据拓展3n个数据，范围从1到30000000，相当于把n个数据分别加上1千万和2千万再加到的后面。

（2）以第n个数为基点按上面方面计算距离和D[n]; result=D[n];

（3）遍历i(n+1<=i<2n),按下面方法D[i-1]计算D[i],若result>D[i],则result=D[i];

(4)输出结果result

#include <stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int P[300000];
int SEG=10000000;
int main()
{
	long n;
	long i;
	long j;
	double result,tempresult;
	
	cin>>n;
	
	for(i=0;i<n;i++)
	{
		cin>>P[i];
		
	}
	sort(P,P+n);
	for(i=0;i<n;i++)
	{
		P[i+n]=P[i]+SEG;
		P[i+2*n]=P[i+n]+SEG;
	}
	tempresult=0;
	int s;
	s=P[n]+SEG/2;
	for(i=n+1;P[i]<=s;++i)
	{
		tempresult+=(P[i]-P[n]);
	}
	int ln=i;
	j=2*n-i;
	for(i=0;i<j;++i)
	{
		tempresult+=(P[n]-P[n-i-1]);
	}
	result=tempresult;
	for(i=n+1;i<2*n;++i)
	{
		s=P[i]+SEG/2;
		for(j=ln;P[j]<=s;j++)
		{
			tempresult+=(P[j]-P[i]);
			tempresult-=(P[i-1]-P[j-n]);
		}
		tempresult+=((n-ln+2*i-j)*(P[i]-P[i-1]));
		ln=j;
		if(result>tempresult)
			result=tempresult;
	}
	printf("%.0f\n",result);
	
	

		
	return 0;
}