torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #215, Division 2, A : Sereja and Coat Rack

概要

n 個の洋服掛けがあり、i 番の洋服掛けは金額 a_i で客人に貸し出す。
この日、m 人の客人がくる。
客人は、到着順にその時点で空いている洋服掛けの内で最も安いものを利用する。
洋服掛けに空きが無いとき、その客人には金額 d を支払う。
この日の収益を求めよ。

解法

a を予め昇順ソートしておくと、先頭から m 個の要素を抜き出した総和が利益になります。
また、n より m が大きいとき、( m - n ) * d が支出です。
これらの総和が答えになります。

コード

main = do
	[ n, d ] <- map read . words <$> getLine
	as <- sort . map read . words <$> getLine
	m <- readLn

	print $ sum ( take m as ) - max 0 ( m - n ) * d