P10708 [NOISG2024 Prelim] Tourist 题解

Eason_cyx · 2024-07-08 09:53:10 · 题解

为了得到最小花费，第 i 天的火车票有两种买法：

• 购买 a_i 张单程票。

• 购买一张单日票。

所以，第 i 天的最小花费就是这两种买法中的最小值。

那么我们依次枚举 n 天的最小花费，加起来就是总的最小花费。

时间复杂度 \Theta(n)。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,m,k; cin >> n >> m >> k;
    int ans = 0;
    for(int i = 1;i <= n;i++) {
        int x; cin >> x;
        ans += min(x * m,k);
    }
    cout << ans << endl;
    return 0;
}