CF1951C

题目描述

点击跳转

思路

将天数按原始票价从小到大排序一遍(此处sort要自定义一下： 若票价相同的情况下，天数升序排列)，由于每次购买后导致后续天数票价提高，开一个cnt来统计累计涨价量，当天的有效价格就是：a[x] + cnt。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long int;

#define akitama return 0

void solve() {
    ll n, m, k; cin >> n >> m >> k;
    vector<ll> a(n+1, 0);
    vector<ll> dp(n, 0);
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        dp[i-1] = i;
    }
    sort(dp.begin(), dp.end(), [&](int x, int y) {
        if (a[x] != a[y]) return a[x] < a[y];
        return x < y;
    });
    ll ans = 0, cnt = 0;
    for (auto x : dp) {
        ll t = min(m, k);
        ans += 1LL * t * (a[x] + cnt);
        cnt += t;
        k -= t;
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int _ = 1; cin >> _;
    while (_--) {
        solve();
    }
    akitama;
}