torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Codeforces #270, B : Design Tutorial: Learn from Life

問題概要

 n 人が一階でエレベーターを待っていて、i 番の人が行きたいフロアは f_i 階である。
 エレベーターには k 人が同時に乗ることができ、a 階から b 階へ移動するのに | a - b | の時間がかかる。また、人の乗り降りにかかる時間は無視できる。
 エレベーターに乗る順番を工夫したとき、全ての利用者が目的の階へ移動した上で、エレベーターが一階に戻ってくるまでの最短時間を求めよ。

解法

 最も上の階に行きたい人に着目します。その人が目的の階に行くとき、他の人もついでに乗って行った方がよいというのは自明に分かることですが、一緒に行く人はより上の階に行きたい人から優先して選んだ方が結果が良くなります。行くべき階の内最も高いところに行くので、誰を一緒に乗せてもコストは増えません。であれば、できるだけ上の階に行きたい人からまとめて運ぶことで、後にエレベーターが行かなければならない階を低くすることができて得です。
 従って、f を降順にソートしてから k 個ずつのグループに分け(末尾は k 個以下のグループ)、( グループの最大値(グループの先頭にある) - 1 ) * 2 の総和をとることで答えが求まります。

コード

using VI = vector<int>;

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

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, k;
	cin >> n >> k;

	VI fs( n );
	copy_n( istream_iterator<int>( cin ), n, fs.begin() );
	transform( ALL( fs ), fs.begin(), bind( minus<int>(), _1, 1 ) );

	sort( ALL( fs ), greater<int>() );

	int res = 0;
	for ( int i = 0; i < n; i += k )
	{
		res += fs[i] * 2;
	}

	cout << res << endl;

	return 0;
}