优先队列

CF1310A Recommendations

题目描述：
https://codeforces.com/problemset/problem/1310/A
给你两个数组 a 和 t，长度相同且不超过 2e5，1<=a[i]<=1e9, 1<=t[i]<=1e5。
每次操作，你可以给某个 a[i]+=1，花费为 t[i]。你可以操作任意多次。
请问要使 a 中所有数字均不相同，最小花费是多少？

题解

// 核心代码gou'zao
static void solve() {
        int n = ni();
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = ni();
        }
        for (int i = 0; i < n; i++) {
            a[i][1] = ni();
        }
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> o2 - o1);
        Arrays.sort(a, (o1, o2) -> (o1[0] - o2[0]));
        long sum = 0, t = 0;
        long cur = 0;
        for (int i = 0; i < n || !q.isEmpty(); i++) {
            if (q.isEmpty()) cur = a[i][0];
            int j = i;
            while (j < n && a[j][0] == cur) {
                q.offer(a[j][1]);
                t += a[j][1];
                j++;
            }
            i = j - 1;
            cur++;
            t -= q.poll();
            sum += t;
        }
        out.println(sum);
    }