問題概要
相異なる $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
