对于多组数据，每次给定 \(n\) 个商品的利润 \(p_i\) 和最晚卖出时间 \(d_i\) 。规定每天只能卖一个没有过期的商品。求最大利润。
这题有俩方法。这里仅介绍并查集做法。考虑用并查集来表示一个天数的使用情况，每个天数的父亲在路径压缩后都指向它及它以前时间最晚的一个空时间。这样能确保货物在不过期的情况下最晚卖出，拥有决策包容性。然后就可以按利润降序排列商品，每次查询该商品能被卖出的最晚可用时间（即其代表元素），若该时间不为 \(0\) 则占用该时间（将该时间的父亲指向上一天）并累计答案。
\(View\) \(Code\)
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int ret=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
ret=(ret<<1)+(ret<<3)+ch-'0';
ch=getchar();
}
return ret*f;
}
int n,fa[10005],maxd,ans;
struct goods
{
int p,d;
}a[10005];
inline bool cmp(goods a,goods b)
{
return b.p<a.p;
}
int get(int x)
{
if(x==fa[x])
return x;
return fa[x]=get(fa[x]);
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
maxd=0;
ans=0;
for(register int i=1;i<=n;i++)
{
a[i].p=read();
a[i].d=read();
maxd=max(maxd,a[i].d);
}
sort(a+1,a+n+1,cmp);
for(register int i=1;i<=maxd;i++)
fa[i]=i;
for(register int i=1;i<=n;i++)
{
int r=get(a[i].d);
if(r)
{
fa[r]=r-1;
ans+=a[i].p;
}
}
printf("%d\n",ans);
}
return 0;
}原文：https://www.cnblogs.com/Peter0701/p/11808506.html