AcWing 145. 超市
原题链接
简单
作者:
ACSaber
,
2020-12-28 11:23:01
,
所有人可见
,
阅读 363
import java.util.*;
class Main {
static int N = 10009;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
if (!sc.hasNext()) break;
int n = sc.nextInt();
int[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
int pi = sc.nextInt();
int di = sc.nextInt();
arr[i] = new int[]{pi, di};
}
Arrays.sort(arr, (a, b) -> {
return a[1] - b[1];
});
// 堆中存放的是所有最终卖出的商品的利润
PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> {
return a - b;
});
for (int[] a : arr) {
int pi = a[0];
int di = a[1];
queue.add(pi);
while (queue.size() > di) {
queue.poll();
}
}
int ans = 0;
while (!queue.isEmpty()) {
ans += queue.poll();
}
System.out.println(ans);
}
}
}