奶牛租赁服务(Rental Service S) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, r;
    if (!(cin >> n >> m >> r)) return 0;
    vector<long long> c(n);
    for (int i = 0; i < n; ++i) cin >> c[i];
    sort(c.begin(), c.end(), greater<long long>());
    vector<pair<long long, long long>> shops(m);
    for (int i = 0; i < m; ++i) {
        cin >> shops[i].second >> shops[i].first;
    }
    sort(shops.begin(), shops.end(), greater<pair<long long, long long>>());
    vector<long long> rent(r);
    for (int i = 0; i < r; ++i) cin >> rent[i];
    sort(rent.begin(), rent.end(), greater<long long>());
    vector<long long> milkPref(n + 1, 0);
    int sIdx = 0;
    for (int i = 0; i < n; ++i) {
        milkPref[i + 1] = milkPref[i];
        long long rem = c[i];
        while (rem > 0 && sIdx < m) {
            long long take = min(rem, shops[sIdx].second);
            milkPref[i + 1] += take * shops[sIdx].first;
            rem -= take;
            shops[sIdx].second -= take;
            if (shops[sIdx].second == 0) ++sIdx;
        }
    }
    vector<long long> rentPref(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        rentPref[i] = rentPref[i - 1] + (i <= r ? rent[i - 1] : 0);
    }
    long long ans = 0;
    for (int i = 0; i <= n; ++i) {
        ans = max(ans, milkPref[i] + rentPref[n - i]);
    }
    cout << ans << "\n";
    return 0;
}