题目地址
贪心：优先选利益最大的商品，从deadline向前推直到都放不了再选下一个商品利益最大的
关键是判断哪一些日子不能再放了，最简单的方法就是一个数组+一个for循环判断
但更快的是用并查集，p=find(deadline) 当p>0，p就是可以放的日子 否则放不了;放好后更新parent[p]=p-1;向前一天递推
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
#include<vector>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
int p[10000+5];
struct product{int deadline,profit;product(int d,int p):deadline(d),profit(p){}bool operator < (const product& p) const {return profit<p.profit;}
};
int find(int x){return p[x]==x?x:p[x]=find(p[x]);
}
int main()
{int T;priority_queue<product> Q;while(scanf("%d",&T)!=EOF){int pf,deadline,maxd=0;while(T--){cin>>pf>>deadline;maxd=max(maxd,deadline);Q.push(product(deadline,pf));}for(int i=0;i<=maxd;i++) p[i]=i;int ans=0,d;while(!Q.empty()){d=find(Q.top().deadline);if(d>0){p[d]=d-1;ans+=Q.top().profit;}Q.pop();}cout<<ans<<endl;}return 0;
}