Python3で解く AtCoder Beginner Contest 153 C - Fennec vs Monster

結構単純。必殺技は大きいものから使っていけばいい。

概要

$n$ 体モンスターがいる。
$k$ 回必殺技が使え、必殺技は一発でモンスター倒せる。
必殺技以外だとモンスターの体力を一回の攻撃で $1$ だけ減らせる。
$i$ 番目のモンスターの体力を $h_i$ とする。
攻撃回数の最小となるように必殺技を適切に使ったあ場合の必殺技を含まない攻撃回数は？

解くときに考えた内容

攻撃回数を最小にしたいので、体力が大きいモンスターから必殺技で倒す。
（つまりソートする必要がある）
必殺技で倒しきれなかったら、残ったモンスターの体力の合計分攻撃する。

コード

n, k = map(int, input().split())
h = [int(x) for x in input().split()]
h_s = sorted(h)
if len(h_s) <= k:
    ans = 0
else:
    for _ in range(k):
        h_s.pop()
    ans = sum(h_s)
print(ans)

参考になる書籍

問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。