Recommendations

Created by LXC on Sat Jul 8 08:43:10 2023

https://codeforces.com/problemset/problem/1310/A

ranting: 1700

tag: data structures, greedy, sortings

problem

给出两个长度都为n的数组a和b，让数组$a_i$增长1的代价是$b_i$。求让a中数互不相同的最小代价。

solution

对于有着相同值的$a_i$，我们只能保留一个就是有着最大$b_i$的$a_i$，其余都增长。

对a和b以二元组(a_i,b_i)字典序升序排序。

我们记录所有需要移动的元素$b_i$的集合，记为S，S中的元素移动代价总和为s。

我们从小到大遍历a数组。

当$a_{i-1} \ne a_i$时，可以将S中的元素尽量的填充到$a_{i-1}+1, a_{i-1}+2, \cdots, a_{i}$。
每次移动时需要保留一个$b_i$最大的元素。可以用优先队列获取最大元素。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<pair<ll, ll>> a(n);
    for (auto& [i, j] : a)
        cin >> i;
    for (auto& [i, j] : a)
        cin >> j;
    sort(a.begin(), a.end());
    // for (auto& [i, j] : a) {
    //     cout << i << " " << j << endl;
    // }
    priority_queue<ll> q;
    ll p = 0, s = 0, ans = 0;
    for (auto [i, j] : a) {
        for (ll k = p; k < i && q.size(); k++) {
            s -= q.top();
            q.pop();
            ans += s;
        }
        s += j;
        q.push(j);
        p = i;
    }
    while (q.size()) {
        s -= q.top();
        q.pop();
        ans += s;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}