TopCoder, SRM 624, Division 2, Level 1 : CostOfDancing

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13195&rd=15857

問題概要

　非負整数からなる列 danceCost と、正整数 K ( ) が与えられる。danceCost から重複せずに K 項を選んだきの総和の最小値を求めよ。

解法

　明らかに、danceCost の内で小さいものから順に採用していくことで総和を小さくできます。従って、std::sort で danceCost を昇順にソートして、先頭から K 項の総和をとることで答えが求まります。総和の計算には std::accumulate を利用できます。

コード

#define ALL( c ) (c).begin(), (c).end()

class CostOfDancing
{
public:
	int minimum( int K, vector <int> danceCost )
	{
		sort( ALL( danceCost ) );
		return accumulate( danceCost.begin(), danceCost.begin() + K, 0 );
	}
};