博客

题意：每个 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);
	}	
}