正经题解｜新年花坛守护战

题面大意

现在有$n$个花坛，每个花坛上有$a_i$个小年兽，你需要驱赶所有的小年兽。

有两种驱赶的方案

幸运福花：消费 $1个$ 金币可以驱赶一个小年兽

烟花炮：消费 $k$个 金币，可以驱赶任意一个花坛上的所有小年兽

题意分析

请问最少花费多少个金币，就可以将小年兽全部驱赶呢？

解题思路

每个花坛只要选择一种方案就行了，然后我们要看是选择幸运福花还是烟花炮，如果某一个花坛上的小年兽数量是小于烟花炮需要的金币数量，那么就选择幸运福花驱赶这个花坛上所有的小年兽，反之选择烟花炮。

时间复杂度解析

遍历所有花坛，进行分析即可，复杂度为$O(n)$。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
int main() {
    int n,c,k;
    cin >> n >> c;
    for(int i=0;i<n;i++) {
        cin >> a[i];
    };
    int r = 0;
    for(int i = 0;i<n;i++) {
        int x = a[i];
        if (x >= c) {
            r += c;
        } else r+=x;
    }
    cout << r << endl;
    return 0;
}