[UVa] 10137 - The Trip

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

題意: 有 n 個同學出去旅行，出遊時為了方便某活動的錢是暫時由某個人付，結束後大家再平分，由於錢有可能無法整除，所以平分後任兩個人所需付的錢不能差超過1塊錢，問最後最少所需移動的總錢數是多少。


解法: 直接算，付越多錢的人要盡量拿少一點錢回來，這樣總移動的錢會最少。

TAG:ad hoc

注意:

程式碼:

	/**
	* Tittle: 10137 - The Trip
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/08
	*/
	// 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 1005
	// declarations
	int n;
	int cost[N];
	int sum;
	// functions
	int abs( int val )
	{
	if( val < 0 ) return -val;
	return val;
	}
	// main function
	int main( void )
	{
	int d, c;
	int per, cnt;
	int ans;
	// input
	while( scanf( "%d", &n )==1 && n ) {
	// init
	sum = 0;
	ans = 0;
	FOR( i, 1, n ) {
	scanf( "%d.%d", &d, &c );
	cost[i] = d*100+c;
	sum += cost[i];
	}
	// solve
	per = sum/n;
	cnt = sum%n;
	sort( cost+1, cost+n+1 );
	for( int i=n; i>=1; --i ) {
	if( cnt ) {
	ans += abs(cost[i]-(per+1));
	--cnt;
	} else
	ans += abs(cost[i]-per);
	}
	ans /= 2;
	printf( "$%01d.%02d\n", ans/100, ans%100 );
	}
	return 0;
	}

view raw 10137 - The Trip.cpp hosted with ❤ by GitHub