torus711 のアレ

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

AtCoder Beginner Contest 171, B : Mix Juice

問題概要

 相異なる $N$ 個の正整数からなる列 $\{ p_i \}$ が与えられる.ここから $K$ 項を選んで和を取るとき,和として有り得る値の最小値を求めよ.

制約

  • $1 \leq K \leq N \leq 1{,}000$
  • $1 \leq p_i \leq 1{,}000$

解法

 ある選び方を固定したとき,その選び方で選んでいない要素であって,選んでいる整数のどれかよりも小さな値が存在するならば,その $2$ 要素を入れ替えることで和を小さくできます.このことから,値の小さな要素から貪欲に選ぶのが最適となります.
 実装としては,まず列を昇順ソートしてから先頭 $K$ 要素の和を求めるのが楽でしょう.この場合,計算量が最も大きくなるのはソート部分で,$O( N \log N )$ 時間となります.

コード

readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

main = do
	[ _, k ] <- readInts
	as <- sort <$> readInts
	print $ sum $ take k as