G - Supermarket

传送门：Supermarket


题意：有n件商品，每件商品的利润为p_i，销售日期的截止时间为d_i（即只能在d_i时间前销售该物品）。一天只能销售一件物品。问这n件商品的最大利润为多少
思路：具体见代码和注释。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10010;int n, ans;
int p[N];
struct node{int p,d;
}s[N];bool comp(node x,node y)
{return x.p>y.p;//按利润从高到低排序
}
int find(int x) {if(x != p[x]) p[x] = find(p[x]);return p[x];
}int main() {while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++) scanf("%d%d",&s[i].p,&s[i].d);for(int i=0;i<N;i++) p[i]=i;sort(s+1,s+1+n,comp);int ans=0;for(int i=1;i<=n;i++){int day=find(s[i].d);if(day)//day为0说明这个物品已经过保质期无法再选{ans+=s[i].p;//父节点直接指向下一个有空的位置（为0就说明没空位了）p[day]=find(day-1);}}printf("%d\n",ans);}
}