本文共 1457 字，大约阅读时间需要 4 分钟。

1097: Meeting Time Limit: 2 Sec  Memory Limit: 64 MB Submit: 10  Solved: 7 [Submit][Status][Web Board] Description There n peoples, they want to meet for discussing something about NBUT ACM Laboratory, so they need to decide a location where they meeting. But they are lazy, they want a location where the summary of each one’s moving distance is least, now you know the n peoples’ position, can you help them to calculate the minimum summary of each one’s moving distance.  Input Input starts with an integer T(1 <= T <= 20), denoting the number of test case. For each test case, first line contains an integer n(1 <= n <= 100000), denoting the number of people. Next line contains n integers Pi(0 <= Pi <= 109), denoting each one’s position. Note that maybe someone stay at the same place.  Output For each test case, print the minimum summary of each one’s moving distance.  Sample Input 1 5 1 2 3 4 5 Sample Output 6 HINT

You can set the location at 3, so the minmum summary of each one’s moving distance is 6(2+1+0+1+2).

找最短路径  sort一下 相对最大的减去相对最小的  只要重复的线段最小就是答案  最短的一般都是在中间

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int main(){	long long n,m,i,k,sum,max,min;	int a[100010];	ios::sync_with_stdio(false);	cin>>k;	while(k--)	{		sum=0;		cin>>n;		memset(a,0,sizeof(a));		for(i=0;i
        
         >a[i]; sort(a,a+n); max=n-1; min=0; while(max>=min) { sum+=a[max]-a[min]; max--; min++; } cout<
         
          <
         
        
       
      
     
    
   

转载地址：http://atfci.baihongyu.com/