[UVa] 10057 - A mid-summer night's dream

題目網址: http://goo.gl/eDJSW1

題意: 給一長度為 n 的數列 Xi，求 A 使得 |X1-A| + |X2-A| + ... + |Xn-A| 最小。



解法: 中位數....。

TAG: Math

注意:

程式碼:

	/**
	* Tittle: 10057 - A mid-summer nights dream
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/10
	* File: 10057 - A mid-summer nights dream.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 1000005
	#define ABS(x) ((x)<0 ? -(x):(x))
	// declarations
	int n;
	int seq[N];
	int cnt[100000];
	int ans1, ans2, ans3;
	// functions
	int calc( int v )
	{
	static int ret;
	ret = 0;
	FOR( i, 0, n-1 )
	ret += ABS( v-seq[i] );
	return ret;
	}
	// main function
	int main( void )
	{
	int med, sum;
	// input
	while( scanf( "%d", &n )==1 ) {
	clr( cnt, 0 );
	FOR( i, 0, n-1 ) {
	scanf( "%d", &seq[i] );
	++cnt[seq[i]];
	}
	// solve
	sort( seq, seq+n );
	med = seq[n/2];
	sum = calc( med );
	for( ans1 = med; n >= 0 && calc(ans1-1)==sum; --ans1 );
	ans2 = ans3 = 0;
	for( int i=ans1, j=seq[n-1]; i <= j && calc(i)==sum; ++i ) {
	ans2 += cnt[i];
	++ans3;
	}
	// output
	printf( "%d %d %d\n", ans1, ans2, ans3 );
	}
	return 0;
	}

view raw 10057 - A mid-summer night's dream.cpp hosted with ❤ by GitHub