需考虑: (1) 在固定的时间内是否可以将所有物品买完; (2) 按物品的价值大小排序;
定义find函数,如果物品所在可售的最大事件未被占用,标记并将物品可售时间缩短1.
在可用时间结束后,ans为最大。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=10010;
int f[Maxn];
struct Node{
int p,d;
}node[Maxn];
bool cmp(Node a,Node b){
return a.p>b.p;
}
int find(int x){
if(f[x]==-1) return x;
return f[x]=find(f[x]);
}
int main(){
int n;
while(scanf("%d",&n)==1){
memset(f,-1,sizeof(f));
for(int i=0;i<n;i++)
scanf("%d%d",&node[i].p,&node[i].d);
sort(node,node+n,cmp);
int ans=0;
for(int i=0;i<n;i++){
int t=find(node[i].d);
if(t>0){
ans+=node[i].p;
f[t]=t-1;
}
}
printf("%d\n",ans);
}
}