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

な場合に注意。。。

問題へのリンク

問題概要

個の正の整数 が与えられる。以下の操作を 回まで行うことができる:

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

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

制約

• 
• 

考えたこと

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

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

という風にすればおおむね OK。ただし、 が 以上である場合は、 個の整数をすべて 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;
}