#UVa:10041-Vito’s Family

取數列之中位數(其實取離中位數最近的兩點所連成的線上任何點皆可),即可求得相減絕對值最小總和。

C++(0.020)

/*******************************************************/
/* UVa 10041 Vito's Family                             */
/* Author: LanyiKnight [at] knightzone.studio             */
/* Version: 2012/03/18                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

int main(){
  int testcase;
  int r, s[505];
  int house, d;
  while( scanf( "%d", &testcase ) != EOF ){
    for( int i = 0 ; i < testcase ; i++ ){
      scanf( "%d", &r );
      for( int j = 0 ; j < r ; j++ )
        scanf( "%d", &s[j] );
      sort( s, s+r );

      d = 0;
      house = s[r/2];
      for( int j = 0 ; j < r ; j++ )
        d += abs( house-s[j] );
      printf( "%d\n", d );
    }
  }
  return 0;
}
廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: