题解 | #最小代价#

基本思想就是先排序，然后从相同a中选出b最大的值，保留，其余的值全加到最终代价中，这个过程用了一个priority_queue更新，每次在a值变换时计算。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
long minprice(vector<vector<int>>& prices);
int main() {
    int n;
    cin >> n;
    vector<vector<int>> prices(n, vector<int>(2));
    for (int i = 0; i < n; i++) {
        cin >> prices[i][0];
    }
    for (int i = 0; i < n; i++) {
        cin >> prices[i][1];
    }
    cout << minprice(prices) << endl;
    return 0;
}

long minprice(vector<vector<int>>& prices) {
    sort(prices.begin(), prices.end(), [](vector<int>& a, vector<int>& b) {
        return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
    });        // 从小到大排序
    priority_queue<int,vector<int>,less<int>> q;
    int cur = prices[0][0];
    long all = 0, res = 0;    // 最后几个用例值很大，需要用long保存
    for(auto const& price : prices){
        if (!q.empty() && price[0] != cur) {
            while (!q.empty() && cur++ != price[0]) {    
                all -= q.top();
                q.pop();
                res += all;
            }
            cur = price[0];
        }
        q.push(price[1]);
        all += price[1];
    }
    while (!q.empty()) {
        all -= q.top();
        q.pop();
        res += all;
    }
    return res;
}