题意：买卖N件东西，每件东西都有个截止时间，在截止时间之前买都可以，而每个单位时间只能买一件。问最大获利。
思路：显然贪心是这道题的方法，如果在商品的最后的日期能买的话，就买，否则看看它之前一天的时间能不能买，依次类推，怎么标记我们能买的日子呢，并查集解决，初始化都是-1，如果被占用了，那么就找前一个节点也就是昨天，直到找到没被占用的日子
#include#include #include #include using namespace std; const int MAXN = 10010; struct node{ int p,d; }arr[MAXN]; int f[MAXN],n; 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(){ while (scanf("%d",&n) != EOF){ memset(f,-1,sizeof(f)); for (int i = 0; i < n; i++) scanf("%d%d",&arr[i].p,&arr[i].d); sort(arr,arr+n,cmp); int ans = 0; for (int i = 0; i < n; i++){ int t = find(arr[i].d); if (t > 0){ ans += arr[i].p; f[t] = t-1; } } printf("%d\n",ans); } return 0; }