超市

前言：肚子好饿哦，我们去超商买点东西吧，好啊，可是我们没钱了欸，你回去拿点了啊，不行的，我爸妈不给我，这里有面包你们要吃吗？好啊，我家还蛮大的，你们可以来我家van（误

题目来源

这道题来自于acwing，下面是链接

145. 超市 - AcWing题库

同时，这道题也可以在算法竞赛进阶指南，POJ，和kuangbin专题里面找到

原题题面

超市里有 N 件商品，每件商品都有利润 pi和过期时间 di，每天只能卖一件商品，过期商品不能再卖。

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

输入格式

输入包含多组测试用例。

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

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

输出格式

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

每个结果占一行。

数据范围

0≤N≤10000
1≤pi , 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

题目解释

朴素算法

我们已知这个超市很独特，每天就卖一件物品哈(早晚得倒闭)，现在我们想知道最高的收益是多少，那这思路就好说力，

我们按照题目要求输入输出数据来进行排序，对于每一个商品我们按照这种排法，价格相同的天数高优先排，价格不同的价格优先排，然后对于每一个商品，我们从它的可以被卖掉的最后一天开始算，如果它的最后一天没有其它商品卖，那么就卖它，反之，我们就看上一天有没有商品卖，对于每一个商品依次进行，可以卖掉的商品的价格累加就是我们的最大的收益

这种思路很正确，可以过一些样例(在洛谷里面有道类似的题就用上面的方法过的，因为数据较少可以跑过)，但是这道题用上面的方法就不太行了，我们对于每一个物品，都要从它可以卖掉的最后一天找起，这样就会很麻烦，会有很多不需要的计算量，这个时候，我们就要对我们的朴素算法进行优化

优化 并查集

我们把所有的天数分成两类，有商品可以卖的天和没有商品卖的天，一开始，我们所有的天都是互不相关的，现在我们从第一个商品开始，把它加到它的最后一天，这样一来，就有一个天数是有商品可以卖的，依次往复，对于每一个商品，我们查询它的可以卖的第一个天数，直接累加就可以了，因为并查集里面的路径压缩近乎O(1)，所以不用担心查询操作的时间，这样一来就节省了很多时间力

代码解释

首先，我们设置基础变量

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
vector<PII> res;
int p[N];

路径压缩

int find(int x) {
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}

主函数

int main()
{
    int n;
    while(cin >> n)
    {
        res.clear();
        int ans = 0, maxx = 0;
        //添加到pair里面
        for(int i = 0;i < n;i++) 
        {
            int a, b;
            cin >> a >> b;
            //pair默认从小到大排序
            res.push_back({-a, b});
            //找到最大天数
            maxx = max(maxx, b);
        }
        //初始化
        for(int i = 0;i <= maxx;i++) p[i] = i;
        //排序(朴素算法里面的，这里直接用stl实现)
        sort(res.begin(), res.end());
        //每个数据进行查询
        for(auto re: res)
        {
            int l = -re.first, r = re.second;
            int t = find(r);
            //判断还有没有天数可以用
            if(p[t] > 0)
            {
                ans += l;
                //变成上一天
                p[t] = t - 1;
            }
        }
        //输出累加和
        cout << ans << endl;
    }
    return 0;
}

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
vector<PII> res;
int p[N];

int find(int x)
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n;
    while(cin >> n)
    {
        res.clear();
        int ans = 0, maxx = 0;
        for(int i = 0;i < n;i++) 
        {
            int a, b;
            cin >> a >> b;
            res.push_back({-a, b});
            maxx = max(maxx, b);
        }
        for(int i = 0;i <= maxx;i++) p[i] = i;
        sort(res.begin(), res.end());
        for(auto re: res)
        {
            int l = -re.first, r = re.second;
            int t = find(r);
            if(p[t] > 0)
            {
                ans += l;
                p[t] = t - 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}