​

Description

给定N个商品

每个商品有利润 p_i 和过期时间 d_i

每天只能卖一个商品，过期商品不能再卖，

求如何安排每天卖的商品，可以使收益最大。

1≤N,p_i,d_i≤10^4。

Format

Input

测试做到文件底结束

对于每组数据，先给出数字N

接下来N行，每行两个数字代表pi与di

Output

如题

Samples

输入数据 1

4  
50 2  
10 1   
20 2   
30 1
7  
20 1   
2 1   
10 3  
100 2   
8 2
5 20  
50 10

输出数据 1

80
185

 题目大意：有n个商品，每个商品都有一个值，第一个是其价值，第二个是其过期日期，每一天只能卖一件商品，问最大利润。

sol1：拿到这个题目第一眼想到的就是贪心，可以先卖贵的，然后每一件商品尽可能晚的卖出

所以可以先按利润排序然后，枚举每个商品用一个vis数组来标记每一个时间点是否被占用，如果找到一个时间点标记为被占用，累加答案；贴出代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct A{
	int x,y;
}a[10050];
int n,ans,t;
bool cmp(A q,A w){
	return q.y>w.y;
}
bool vis[10050];
signed main(){
	while(cin>>n){
		ans=0;
		for(int i=1;i<=n;i++)
			cin>>a[i].y>>a[i].x;
		memset(vis,0,sizeof(vis));
		sort(a+1,a+n+1,cmp);//按利润排序 
		for(int i=1;i<=n;i++)
			for(int j=a[i].x;j>=1;j--){//找一个最晚的空余时间点 
				if(vis[j]==0){//如果找到一个空余时间点 
					vis[j]=1;//标记为被占用 
					ans+=a[i].y;
					break;
				}
			}
		cout<<ans<<'\n';
	}
	return 0;
}

时间复杂度O(n^2),可以通过此题；

sol2:考虑优化， 找一个最晚的空余时间点的时候用了一个for循环枚举太过浪费，可以用并查集优化，可以建立一个关于天数的并查集，对于每个商品，若它在d天只有过期，就在并查集中查询d的根R，若R大于0，则安排在第R天卖出，然后把R和R-1合并（还是不懂可以手动在纸上画一下），代码：

#include<bits/stdc++.h>
#define in long long
using namespace std;
int f[10010],n,r,sum;
struct A{
	int t,w;
}a[10010];
bool cmp(A q,A w){
	return q.w>w.w;
}
int find(int x){
	if(f[x]!=x) f[x]=find(f[x]);
	return f[x];
}
signed main(){
	while(cin>>n){
		sum=0;
		for(int i=1;i<=1e4;i++)
			f[i]=i;
		for(int i=1;i<=n;i++)
			cin>>a[i].w>>a[i].t;
		sort(a+1,a+n+1,cmp);//按利润排序 
		for(int i=1;i<=n;i++){
			r=find(a[i].t);//寻找d的根 
			if(r>0){//如果r>0 
				f[r]=r-1;//将r和r-1合并 
				sum+=a[i].w;
			}
		}
		cout<<sum<<"\n";
	}
	return 0;
}

时间复杂度O(nlogn) ,相对于第一种，优化了不少；

sol3:还可以考虑，另一种贪心，用堆来优化先按时间排个序，然后依次放入堆中，如果还有可用时间 ，直接压入堆中，否则每次用利润大的替换小的；代码：

#include<bits/stdc++.h>
#define in long long
using namespace std;
int n,r,sum,now;
struct A{
	int t,w;
}a[10010];
bool cmp(A q,A w){
	return q.t<w.t;
}
priority_queue<int, vector<int>, greater<int> > q;//建立一个小根堆 
signed main(){
	while(cin>>n){
		sum=0;now=0;
		for(int i=1;i<=n;i++)
			cin>>a[i].w>>a[i].t;
		sort(a+1,a+n+1,cmp);//按时间排序 
		for(int i=1;i<=n;i++){
			if(now<a[i].t){//如果还有可用时间 
				now++;//已占用时间+1 
				q.push(a[i].w);//压入堆中 
			}else if(q.size()>0&&a[i].w>q.top()){//如果利润大于堆顶 
				q.pop();
				q.push(a[i].w);//用大的替换小的 
			}
		}
		while(!q.empty()){
			sum+=q.top();
			q.pop();
		}
		cout<<sum<<"\n";
	}
}

时间复杂度O(nlogn) ，和并查集做法差不多