题意:每个 n 的商品的利润和出售截止时间,每天只能卖出一件,且商品超出截止时间就无法出售,问可获得最大的利润;
分析:数据范围给得不大,很容易可以想到贪心:按利润从大到小排序然后遍历,优先填充截止的最后一天并标记,不行就把时间往前遍历找到没有被标记过的然后填充;
但是配合并查集可以降低复杂度,并查集维护每个日期往前最近的空余位,这样子就优化了上述往前遍历找空余的过程;
(表述不怎么好,代码瞅瞅就很好明白了)
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1E4+10;
struct node{
int p,d;
node(){}
node(int _p,int _d){
p=_p,d=_d;
}
bool operator < (const node& a)const{
return p>a.p;
}
}e[N];
int fa[N],n;
int find(int x){
if(fa[x]==-1) return x;
return fa[x]=find(fa[x]);
}
int main()
{
while(~scanf("%d",&n)){
for(int i=1,p,d;i<=n;i++){
scanf("%d%d",&p,&d);
e[i]=node(p,d);
}
sort(e+1,e+n+1);
for(int i=0;i<N;i++) fa[i]=-1;
int ans=0;
for(int i=1;i<=n;i++){
int f=find(e[i].d);
if(f>0){
fa[f]=f-1; //这个点使用了,往前提;
ans+=e[i].p;
}
}
printf("%d\n",ans);
}
}
版权声明:本文为weixin_43209425原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。