概要
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
