AcWing 145. 超市（优先队列 / 并查集）

本文主要是介绍AcWing 145. 超市（优先队列 / 并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

超市里有N件商品，每个商品都有利润pi和过期时间di,每天只能卖一件商品，过期商品（即当天di<=0）不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

输入格式
输入包含多组测试用例。

每组测试用例，以输入整数N开始，接下里输入N对pi和di，分别代表第i件商品的利润和过期时间。

在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。

输出格式
对于每组产品，输出一个该组的最大收益值。

每个结果占一行。

数据范围
0≤N≤10000,
1≤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 <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int maxn = 1e5 + 7;struct Node
{int p,d;bool operator < (const Node&rhs)const{return d < rhs.d;}
}a[maxn];priority_queue<int,vector<int>,greater<int> >Q;int main()
{int n;while(~scanf("%d",&n)){for(int i = 1;i <= n;i++){scanf("%d%d",&a[i].p,&a[i].d);}sort(a + 1,a + 1 + n);for(int i = 1;i <= n;i++){if(a[i].d > Q.size()){Q.push(a[i].p);}else if(a[i].d == Q.size() && a[i].p > Q.top()){Q.pop();Q.push(a[i].p);}}int ans = 0;while(!Q.empty()){ans += Q.top();Q.pop();}printf("%d\n",ans);}return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int maxn = 1e5 + 7;int fa[maxn];struct Node
{int p,d;bool operator < (const Node&rhs)const{return p > rhs.p;}
}a[maxn];priority_queue<Node>Q;int findset(int x)
{if(fa[x] == x)return x;return fa[x] = findset(fa[x]);
}void Union(int x,int y)
{int fx = findset(x),fy = findset(y);if(fx != fy) fa[fx] = fy;
}int main()
{int n;while(~scanf("%d",&n)){int cnt = 0;int mx = 0;for(int i = 1;i <= n;i++){scanf("%d %d",&a[i].p,&a[i].d);mx = max(mx,a[i].d);}sort(a + 1,a + 1 + n);for(int i = 1;i <= mx;i++)fa[i] = i;int ans = 0;for(int i = 1;i <= n;i++){int now = findset(a[i].d);if(now > 0){
//                Union(now,now - 1);fa[now] = now - 1;ans += a[i].p;}}printf("%d\n",ans);}return 0;
}