超市里有N件商品，每个商品都有利润pipi和过期时间didi,每天只能卖一件商品，过期商品（即当天di<=0di<=0）不能再卖。
求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
输入格式
输入包含多组测试用例。
每组测试用例，以输入整数N开始，接下里输入N对pipi和didi，分别代表第i件商品的利润和过期时间。
在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。
输出格式
对于每组产品，输出一个该组的最大收益值。
每个结果占一行。
数据范围
0≤N≤100000≤N≤10000,
1≤pi,di≤100001≤pi,di≤10000
输入样例：
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2
5 20 50 10
输出样例：
80
185算法：贪心 + 小根堆
题解：根据题意，一天只能卖一个商品，那么，我们就可以用贪心的思想来实现，用小根堆（可以用优先队列来实现，不一定要手写）来维护最大值。
优先队列实现小根堆：
#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
#include <algorithm> using namespace std; const int maxn = 1e5+; struct node {
int pi, di;
}arr[maxn]; priority_queue<int, vector<int>, greater<int> > p; //建立从小到大的优先队列（小根堆） bool cmp(node a, node b) {
return a.di < b.di;
} int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = ; i <= n; i++) {
scanf("%d %d", &arr[i].pi, &arr[i].di);
}
sort(arr + , arr + n + , cmp);
for(int i = ; i <= n; i++) {
if(arr[i].di > p.size()) { //如果商品的过期天数大于当前天数，就直接进入队列
p.push(arr[i].pi);
} else if(arr[i].di == p.size() && arr[i].pi > p.top()) { //当商品的过去天数等于当前天数的时候，就比较一下当前商品是否比队列中最小的商品大，如果是就进入队列
p.pop();
p.push(arr[i].pi);
}
}
int ans = ;
while(!p.empty()) {
ans += p.top();
p.pop();
}
printf("%d\n", ans);
}
return ;
}
二叉堆实现小根堆：
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std; const int maxn = 1e5+; struct node {
int pi, di;
}arr[maxn];
int heap[maxn];
int tot; bool cmp(node a, node b) {
return a.di < b.di;
} void up(int n) {
while(n > ) {
if(heap[n] < heap[n / ]) {
swap(heap[n], heap[n / ]);
}
n /= ;
}
} void insert(int val) {
heap[++tot] = val;
up(tot);
} void down(int n) {
int s = n * ;
while(s <= tot) {
if(s < tot && heap[s] > heap[s + ]) { //找出左右子树中较小的那个
s++;
}
if(heap[s] < heap[n]) {
swap(heap[s], heap[n]);
}
n = s;
s = * n;
} } void update(int val) {
heap[] = val;
down();
} int main() {
int n;
while(~scanf("%d", &n)) {
for(int i = ; i <= n; i++) {
scanf("%d %d", &arr[i].pi, &arr[i].di);
}
sort(arr + , arr + n + , cmp);
tot = ;
for(int i = ; i <= n; i++) {
if(arr[i].di > tot) {
insert(arr[i].pi);
} else if(arr[i].di == tot && arr[i].pi >heap[]) {
update(arr[i].pi);
}
}
int ans = ;
for(int i = ; i <= tot; i++) {
ans += heap[i];
}
printf("%d\n", ans);
}
return ;
}
并查集：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm> using namespace std; const int maxn = 1e4+; struct node {
int weight, date;
friend bool operator < (node a, node b) {
if(a.weight == b.weight) {
return a.date > b.date;
}
return a.weight > b.weight;
}
}; vector<node> v;
int f[maxn]; int find(int x) {
if(f[x] != x) {
return f[x] = find(f[x]);
}
return f[x];
} int main() {
int n;
while(~scanf("%d", &n)) {
v.clear();
int maxe = ;
for(int i = ; i < n; i++) {
int x, y;
scanf("%d %d", &x, &y);
v.push_back((node){x, y});
maxe = max(maxe, y);
}
for(int i = ; i <= maxe; i++) {
f[i] = i;
}
sort(v.begin(), v.end()); //按权值从大到小排序
int size = v.size();
int ans = ;
for(int i = ; i < size; i++) {
int w = v[i].weight;
int d = v[i].date;
int pos = find(d); //找到当前日期的最佳位置
if(pos > ) { //如果该位置没有出界，那么就可以使用
ans += w;
f[pos] = pos - ;
}
}
printf("%d\n", ans);
}
return ;
}