题解 | #Supermarket#

Supermarket

https://ac.nowcoder.com/acm/problem/106053

题面(摘自vj: https://vjudge.net/problem/POJ-1456#author=yuming)

超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.
每天只能卖一个商品.
现在你要让超市获得最大的利润.
多组数据.
INPUT
每组数据第一行为N, 即超市的商品数目
之后N行数字. 第i行为 pi, di
N , pi, di <= 10000
OUTPUT
对于每一组数据, 输出当前条件下超市的最大利润

我能想到的解法有两个,都是从不同方面进行贪心

反悔贪心

看到题第一眼就想到，这不就是个标准的反悔贪心题吗，不了解的朋友还是可以去了解一下。
网上一位佬的反悔贪心博客：https://djy-juruo.blog.luogu.org/qian-tan-fan-hui-tan-xin
这里只提一嘴,可以这样做(~懒)

代码很大，你忍一下

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<sstream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pdd pair<double,double>
#define ll long long
#define F first
#define S second
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define abs(a) ((a)<0))?(-1*(a)):(a)
#define INF 0x3f3f3f3f
#define INPUTi1(a) scanf("%d",&(a))
#define INPUTi2(a,b) scanf("%d %d",&(a),&(b))
#define INPUTi3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define INPUTd1(a) scanf("%lf",&(a))
#define INPUTd2(a,b) scanf("%lf %lf",&(a),&(b))
#define INPUTd3(a,b,c) scanf("%lf %lf %lf",&(a),&(b),&(c))
using namespace std;
const int N=10010;
struct node{
    int p,d;
};
bool cmp(node n1,node n2){
    if(n1.d!=n2.d)
        return n1.d<n2.d;
    return n1.p>n2.p;    
}
node e[N];
int main(){
    int n;
    while(~INPUTi1(n)){
        for(int i=0;i<n;i++){
            INPUTi2(e[i].p,e[i].d);
        }
        sort(e,e+n,cmp);
        priority_queue<int,vector<int>,greater<int> >pq;
        long long res=0;
        int cnt=0;
        for(int i=0;i<n;i++){
            if(cnt<e[i].d){
                cnt++;
                res+=e[i].p;
                pq.push(e[i].p);
            }else{
                if(e[i].p>pq.top()){
                    res+=(e[i].p-pq.top());
                    pq.pop();
                    pq.push(e[i].p);
                }
            }
        }
        cout<<res<<"\n";
    }
}

并查集优化贪心

按照正常的贪心想法,因为每天只能卖一件物品。所以我们对于某一天来说，应该优先卖贵的。
为了使得更多天数可以被利用，减少冲突，每一件商品应该等到快过期时卖掉(时间尽量靠后)。这样可以腾出更多天数给其他商品

因此,将商品价格从大到小排序，然后对于每一个商品枚举天数。找到可以卖出的最靠后的某一天，标记之。
但是这样是暴力的贪心，暴力枚举天数会导致超时

可以采用并查集优化这个贪心，这个并查集的写法和普通的并不相同,姑且称之为类并查集

我们观察从后往前观察天数可以发现，如果某天被占用，则会向前找，直到找到一个没有被利用的为止
暴力解法的暴力在于,会重复枚举到被占用的天数。如果能像并查集一样，直接找到根节点/代表元素/最后的没有被占用的天数就好了
初始时给并查集数组 $p[i]$ 赋值为-1代表其未被占用。之后如果要选择这一天，且未被占用，令 $p[i]=i-1$ ,下一次选这一天的时候就直接找到第 $i-1$ 天。这样合并并查集,对于所有不能选择的天数,最终都会指向0
并查集的具体实现参见代码

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<sstream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define pll pair<long long,long long>
#define pii pair<int,int>
#define pdd pair<double,double>
#define ll long long
#define F first
#define S second
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define abs(a) ((a)<0))?(-1*(a)):(a)
#define INF 0x3f3f3f3f
#define INPUTi1(a) scanf("%d",&(a))
#define INPUTi2(a,b) scanf("%d %d",&(a),&(b))
#define INPUTi3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define INPUTd1(a) scanf("%lf",&(a))
#define INPUTd2(a,b) scanf("%lf %lf",&(a),&(b))
#define INPUTd3(a,b,c) scanf("%lf %lf %lf",&(a),&(b),&(c))
using namespace std;
const int N=10010;
struct node{
    int p,d;
};
bool cmp(node n1,node n2){
    return n1.p>n2.p;    
}
node e[N];
int p[N];
int find(int u){
    if(p[u]==-1)
        return u;
    p[u]=find(p[u]);
    return p[u];
}
int main(){
    int n;
    while(~INPUTi1(n)){
        for(int i=0;i<n;i++){
            INPUTi2(e[i].p,e[i].d);
        }
        sort(e,e+n,cmp);
        for(int i=0;i<N;i++)
            p[i]=-1;
        long long res=0;
        for(int i=0;i<n;i++){
            int pi=find(e[i].d);
            if(pi){
                res+=e[i].p;
                p[pi]=pi-1;
            }

        }    
    cout<<res<<"\n";

    }
}