torus711 のアレ

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

Codeforces 159, A : Sockets

概要

n 個のテーブルタップがあり、各タップは a_i 個の差込口を持っている。
さらに、m 個のデバイスと k 個のコンセントがある。
最小で幾つのタップを使うことで、全てのデバイスを接続することができるか答えよ。
全てのタップを使っても接続できない場合は -1 を出力せよ。

解法

一つのタップで、コンセントを一つ使い、a_i のコンセントを増やすことができます。
差込口の数が多い順にタップを使っていけばよいです。

コード

import Control.Applicative
import Control.Monad
import Data.List

main = do
	[ n, m, k ] <- map read . words <$> getLine
	as <- reverse . sort . map read . words <$> getLine
	print $ solve as m k 0

solve :: [Int] -> Int -> Int -> Int -> Int
solve [] m k res
	| k < m = -1
	| otherwise = res
solve (a:as) m k res
	| k < m = solve as m ( k - 1 + a ) ( res + 1 )
	| otherwise = res