超市(并查集和优先队列)

  • 时间:
  • 来源:互联网
  • 文章标签:

超市(并查集和优先队列)

原题链接 https://www.acwing.com/problem/content/description/147/

超市里有N件商品,每件商品都有利润 p i p_i pi和过期时间 d i d_i di 每天只能卖一件商品,过期商品不能再卖。

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

输入格式

输入包含多组测试用例。

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

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

输出格式

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

每个结果占一行。

数据范围

0≤N≤100000
1≤ p i p_i pi, d i d_i di≤10000
最多有14组测试样例

输入样例:

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

一 优先队列

将n件商品按过期时间从小到大排序,然后不断的往优先队列里面插入,分两种情况插入。
优先队列里数的个数也就是表示卖出的商品数也就是天数 size

如果到了第i个数插入,

1,size< d i d_i di 直接插入,因为这时候你经过的天数并没有到你的保质期

2,size>= d i d_i di 这时候将第i个商品的利润和队列里利润最小的一个进行比较,利润大的留在队列里。

因为将过期时间按从小到大排序了,所以如果 d i d_i di <=size 的话 d i d_i di肯定等于size;

#include <bits/stdc++.h>
using namespace std;
const int N=10100;
priority_queue<int,vector<int>,greater<int> > p;//小顶堆 
pair<int,int> a[N];
int n,m,i,j;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if (n==0)
        {
            puts("0");
            continue;
        }
        for(int i=1; i<=n; i++)
        {
            cin>>a[i].second>>a[i].first;//pair排序是以first为第一关键字,因为我们是时间为第一关键字,所以我们读入权值是第二关键字
        }
        sort(a+1,a+1+n);//将日期从小到大排序 
        for(int i=1; i<=n; i++)
        {
            if (a[i].first>p.size())
                p.push(a[i].second);
            else if(a[i].first==p.size() && a[i].second>p.top())
            {
                p.pop();
                p.push(a[i].second);
            }
        }
        long long ans=0;
        while(!p.empty())
        {
            ans+=p.top();
            p.pop();
        }
        printf("%lld\n",ans);
    }
    return 0;
}


二、并查集

这个思路比优先队列快了三倍

首先我们将利润从大到小排序,每次扫描到一个商品;往前找空位,如果有的话就可以卖出去,否则不能

f[i]表示第i个数前面的空位,这个并查集就是将空位和商品连起来

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 233;
pair<int,int> p[maxn];
int f[maxn];//f[i]表示第i个商品前的空位 
int ff(int x)//查找祖宗; 
{
    if(f[x] == x) return x;
    return f[x] = ff(f[x]);
}
bool cmp(pair<int ,int>a,pair<int ,int>b)
{
	return a.first>=b.first;
}
//并查集是将空位和第i个数连通 
int main()
{
    int n;
    while(cin >> n)
    {
        int ans = 0;


        for(int i = 0; i < n; i++)
        {
            cin>>p[i].first>>p[i].second;
        }
        for(int i = 0; i <= maxn; i++) f[i] = i;
        sort(p,p+n,cmp);
        for(int i = 0; i <n; i++)
        {
            int v = p[i].first, e = p[i].second;
            int pos = ff(e);//查找前面的空位 
            if(pos > 0)//有空位 
            {
                ans += v;
                f[pos] = pos - 1;//空位往前移动 
            }
        }
        printf("%d\n", ans);
    }
}

本文链接http://www.taodudu.cc/news/show-1781913.html