Supermarket

题目

超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.
每天只能卖一个商品.
现在你要让超市获得最大的利润.

分析

首先涉及到最大利润，那么我们到方案要尽可能到让利润大的商品卖出去，可以考虑利润从大到小排序发现一些什么性质。当我们选择了当前利润最大的商品，我们需要考虑：
1.查询他的当前截止日期，如果已经过期了，就不卖了。
2.如果卖掉这个商品，截止日期在他之后的所有商品相当于保质期天数-1

并查集怎么去实现

这里有一点难思考，我们用一个数组fa[]来保存商品的截止日期，如果一件商品的截止日期是d，fa[d] = -1,就表示第d天还没卖东西，当我们把此商品卖出后，需要修改fa[d] = d-1,就是说此时又来了一个截止日期是d的，他就需要去d-1天卖，因为第d天已经用过了,如果fa[d-1] = d-2,表示d-1天也被用了。直到fa[c] = -1,表示第c天没有卖东西，这时候就可以卖了。当前这里的遍历需要压缩一下路径，提升到O(1)复杂度

一句话：当某个商品卖掉，他的截止时间是d，就需要把第d天删除掉，也就是fa[d] = d-1,跳过了第d天

AC 代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;

int N;
int fa[maxn];
struct node{
    int p,d;
    bool operator < (const node& o)const{
        return p>o.p;
    }
}arr[maxn];

void init(){
    memset(fa,-1,sizeof(int)*10010);
}
int find(int x){ //查询原来是x截止日期，现在的截止日期是多少
    if(fa[x] == -1) return x;
    else return fa[x] = find(fa[x]);
}
int main(){
    int a,b;
    while(~scanf("%d",&N)){
        init();
        int res = 0;
        for(int i = 1;i<=N;i++){
            scanf("%d%d",&a,&b);
            arr[i] = {a,b};
        }
        sort(arr+1,arr+N+1);
        for(int i = 1;i<=N;i++){
            int t = find(arr[i].d);
            if(t>0){ //如果前d天都用了，并查集就会查询的截止日期就会是第0天
                res += arr[i].p;
                fa[t] = t-1;
            }
        }
        printf("%d\n",res);
    }

    return 0;
}