TopCoder SRM 592, Division 2, Level 1 : LittleElephantAndBooks

概要

N 冊の本があり、それぞれのページ数が与えられる。
これらの本のうち、丁度 number 冊を読む。
次の条件を満たす読み方をしたときの、読んだページ数の最小値を求めよ。

• 読んだページ数が最小ではない
• 上の条件を満たす読み方の内、読んだページ数が最小

解法

まず、読んだページ数が最小になる読み方を計算します。
これは、pages を昇順ソートして先頭から numbers の総和を取った値です。
このとき選ばれた本と、そうでない本を一冊ずつ交換して解を得る方法を考えます。

選ばれた本（のページ数）の集合を A、 それ以外の本の集合を B と呼びます。
このとき、a ∈ A かつ b ∈ B なる本 a, b, を交換して増えるページ数は b - a です。
そのような値の最小値は B の最小値 - a の最大値 です。
A の総和にこの値を足すことで答えが得られます。

コード

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

class LittleElephantAndBooks
{
public:
	int getNumber( vector <int> pages, int number )
	{
		const int N = pages.size();

		sort( ALL( pages ) );
		return accumulate( pages.begin(), pages.begin() + number, 0 ) - pages[ number - 1 ] + pages[ number ];
	}
};