[算法竞赛进阶指南]Supermarket(二叉堆，并查集)

Bertha 。 2022-04-24 11:22 121阅读 0赞

# [poj-1456.Supermarket][] #

### Description ###

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

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

### Input ###

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

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

0 ≤ N ≤ 10000  
1 ≤ pi,di ≤ 10000

### Output ###

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

每个结果占一行。

### Sample Input ###

4  50 2  10 1   20 2   30 1
    
    7  20 1   2 1   10 3  100 2   8 2
       5 20  50 10

### Sample Output ###

80
    185

### 二插堆(小根堆) ###

先按照过期时间从小到大排序，建立一个初始为空的小根堆(节点权值为商品利润)，然后扫描每个商品:

1.  若当前商品的过期时间t等于当前堆中商品的个数，则说明在目前方案下，前t天已经安排了t个商品卖出。此时，若当前商品的利润大于堆顶权值(即已经安排的t个商品中的最低利润),则替换掉堆顶(用当前商品替换掉原方案中利润最低的商品)。
2.  若当前商品的过期时间大于当前堆中的商品个数，直接把商品插入堆。
3.  最终，堆里的所有商品就是我们需要卖出的商品，他们的利润之和就是答案。

#include <iostream>
    #include <queue>
    #include <algorithm>
    using namespace std;
    const int MAX = 10010;
    struct Store{ 
        int profit; // 利润
        int days; // 保质期
    
    };
    
    bool cmp(Store a,Store b) // 按过期时间从小到大排序
    { 
        return a.days < b.days;
    }
    bool operator < (const Store &a,const Store &b){  // 按利润从大到小排序
        return a.profit > b.profit;
    }
    Store s[10010];
    int n;
    priority_queue<Store> q;
    int main()
    { 
        /* freopen("test.txt","r",stdin); */
        while(cin>>n){ 
            while(!q.empty())
                q.pop();
            for(int i = 0;i < n;i++){ 
                cin >> s[i].profit >> s[i].days;
            }
            sort(s,s+n,cmp);
            for(int i = 0;i < n;i++)
            { 
                if(q.empty()) q.push(s[i]);
                else if(s[i].days > (int)q.size()) q.push(s[i]);
                else if(q.top().profit < s[i].profit){ 
                    q.pop();
                    q.push(s[i]);
                }
            }
            int ans = 0;
            while(!q.empty()){ 
                ans += q.top().profit;
                q.pop();
            }
            cout << ans <<endl;
        }
        return 0;
    }

### 贪心+并查集 ###

优先考虑卖出利润大的商品，对每个商品在它过期之前尽量晚卖出。  
把商品按照利润从大到小排序，并建立一个关于天数的并查集，起初每一天各自构成一个集合。对每个商品，若它在d天之后过期，就在并查集中查询d的树根(记为r)，若r大于0，则把该商品安排在第r天卖出，合并r与r-1，答案累加该商品的利润。

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    struct item{ 
        int p; //利润
        int d; //天数
        bool operator < (const item &b) const { 
            return p > b.p;
        }
    };
    
    int t;
    int father[10005];
    item num[10005];
    int get(int x){ 
        if(x == father[x]) return x;
        return father[x] = get(father[x]);
    }
    int main(){ 
        while(cin >> t){ 
            int m = 0,ans = 0;
            for(int i = 0; i < t; i++){ 
                cin >> num[i].p >> num[i].d;
                m = max(m,num[i].d);
            }
            sort(num,num+t);
            for(int i = 0;i <= m;i++){ 
                father[i] = i;
            }
            for(int i = 0;i < t;i++){ 
                int day = get(num[i].d);
                if(day == 0) continue;
                ans += num[i].p;
                father[day] = get(day - 1);
            }
            cout << ans << endl;
        }
        return 0;
    }

[poj-1456.Supermarket]: http://poj.org/problem?id=1456