けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 153 C - Fennec vs Monster (300 点)

 N \lt K な場合に注意。。。

問題へのリンク

問題概要

 N 個の正の整数  H_{1}, \dots, H_{N} が与えられる。以下の操作を  K 回まで行うことができる:

  • 整数を 1 つ選んで、0 にする

操作を行った後の、整数の総和として考えられる最小値を求めよ。

制約

  •  1 \le N \le 2 \times 10^{5}
  •  0 \le K \le 2 \times 10^{5}

考えたこと

素朴に考えれば、 H が大きい順に 0 にしていくと良さそうである。よって解法としては

  •  H が大きい順にソートする
  • 大きい順に  K 個を 0 にする
  • 残った値の和を求める

という風にすればおおむね OK。ただし、 K N 以上である場合は、 N 個の整数をすべて 0 にした時点で処理を打ち切って良い。むしろこのことを失念すると、配列外参照とかのバグに悩むことになるかもしれないので注意。。。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<long long> H(N);
    for (int i = 0; i < N; ++i) cin >> H[i];
    
    sort(H.begin(), H.end(), greater<long long>());
    for (int i = 0; i < min(N, K); ++i) H[i] = 0;
    long long res = 0;
    for (int i = 0; i < N; ++i) res += H[i];
    cout << res << endl;
}