【pythonでABC153を解説】C - Fennec vs Monster

問題概要

問題ページ

問題文

フェネックは \(N\) 体のモンスターと戦っています。

\(i\) 番目のモンスターの体力は \(H_i\) です。

フェネックは次の \(2\) 種類の行動を行うことができます。

• 攻撃：モンスターを \(1\) 体選んで攻撃することで、そのモンスターの体力を \(1\) 減らす
• 必殺技：モンスターを \(1\) 体選んで必殺技を使うことで、そのモンスターの体力を \(0\) にする

攻撃と必殺技以外の方法でモンスターの体力を減らすことはできません。

全てのモンスターの体力を \(0\) 以下にすればフェネックの勝ちです。

フェネックが \(K\) 回まで必殺技を使えるとき、モンスターに勝つまでに行う攻撃の回数 (必殺技は数えません) の最小値を求めてください。

制約

• \(1 \leq N \leq 2 \times 10^5\)
• \(0 \leq K \leq 2 \times 10^5\)
• \(1 \leq H_i \leq 10^9\)
• 入力中のすべての値は整数である。

問題の考察

問題文から必殺技をどのターゲットに使用すれば効率良く敵を倒せるか考えれば良い。

必殺技は体力を\(0\)にすることができるので体力が多いターゲットに使用したほうが効率が良いことがすぐに分かる。

あとは問題文の「攻撃の回数 (必殺技は数えません) の最小値を求めてください。」という部分にだけ気を付けて実際のコードを書けばよい。

ターゲットを体力の多い順にソートして必殺技で倒せるターゲット以外の体力を合計した値がモンスターを殲滅するまでに必要な攻撃回数となる。

たびすけ

C問題レベルではソートしてから処理するといったような前処理が必要な問題が出題されることがあります。

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    h = list(map(int, input().rstrip('\n').split()))
    h.sort()
    t = 0
    for i in range(n - k):
        t += h[i]
    print(t)


if __name__ == '__main__':
    solve()