HDU 2083:簡易版の最短距離

クリックしてタイトルリンクを開く
簡易版の最短距離Time Limit:1000/1000 MS(Java/others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8331    Accepted Submission(s): 3661
Problem Description
冬休みの时、ACBOYは多くの友达を访问して、ちょうど彼のすべての友达の家はすべて座標平面のX軸の上にあります.ACBOYは友人の家を任意に選んで訪問を開始することができるが、訪問するたびに出発点に戻らなければならず、次の友人を訪問することができない.
例えば4人の友人がいて,対応するX軸座標はそれぞれ1,2,3,4である.ACBOYが座標が2の点を出発点として選択した場合、彼が最終的に必要とする時間は|1-2|+|2-2|+|3-2|+|4-2|=4である.
今N人の友达の座標を与えて、それではACBOYはどのように歩いてやっと時間が最も少ないことができますか?
 
Input
入力は、まず正の整数Mであり、M個のテストインスタンスを表す.各例の入力は2行あり、まず正の整数N(N<=500)であり、N人の友人がいることを示す、次の行はN個の正の整数であり、具体的な座標(すべてのデータが<=10000)を示す.
 
Output
各テストインスタンスについて、すべての友人にアクセスするのにかかる最小時間を出力し、各インスタンスの出力が1行を占めます.
 
Sample Input

       
       
       
       

        
        
        
        2
2 
2 4 
3 
2 4 6
       
       
       
       

 
Sample Output

       
       
       
       

        
        
        
        2
4
       
       
       
       

 
Source
2006/1/15 ACMプログラム設計期末試験
 
Recommend
lcy
 
============================================================
求めます:X軸の上のn個の定点の中ですべての定点までの距離と最小の点.
まず、すべての点をX軸方向に並べ替えた後、条件i+j=n+1を満たす2つの点PiとPjをシーケンス対称群として編成する.
では,シーケンス番号中点Pmは任意のシーケンス番号対称群(Pi,Pj)に対してPi<=Pm<=Pjである.
基準:2つのポイントまでの距離と最小のポイントは、それら自体とそれらの間の任意のポイントであり、最小の距離とそれらの間の距離に等しい.
Pmは任意のシーケンス番号対称群に対して最小距離和をとることが分かる.
したがって,Pmも全定点までの最小距離和,最小距離和が全シーケンス対称群に等しい区間長和を取得する.
==================================================

#include <cmath>  
#include <cstdio>  
#include <algorithm>  
  
using namespace std;  
  
int M, N, P[ 505 ];

int main()  
{  
    while( scanf( "%d", &M ) == 1 ) while( M-- )
    {
        scanf( "%d", &N );
        for( int i = 0 ; i < N ; ++i )
        {
            scanf( "%d", &P[ i ] );
        }
        sort( P, P + N );
        int result = 0;
        for( int i = 0, j = N - 1 ; i < j ; ++i, --j )
        {
            result += P[ j ] - P[ i ];
        }
        printf( "%d
", result );
    }
    return 0;  
}