【超市】
【问题描述】
超市里有N件商品，每个商品都有利润pi和过期时间di,每天只能卖一件商品，过期商品（即当天di<=0）不能再卖。求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。
【输入格式】
输入包含多组测试用例，测试用例最多30组。
每组测试用例，以输入整数N开始，接下里输入N对pi和di，分别代表第i件商品的利润和过期时间。
在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。
【输出格式】
对于每组产品，输出一个该组的最大收益值。每个结果占一行。
【样例输入】
4 50 2 10 1 20 2 30 1
7 3 1 2 1 10 3 100 2 8 2 1 20 50 10
【样例输出】
80
169
数据范围
0≤N≤10000,1≤pi,di≤10000
分析：
每天只能卖一件，过期不能卖。我们的任务是合理规划商品的卖出日期，使得收益最大。
贪心：按利润大小顺序，规划卖出时间，尽可能晚点卖，这样可能会给保质期短的商品留有更多选择机会。
先将商品按利润从大到小排序，然后按顺序规划卖出日期。卖出时间为，可以卖出的日期中的最晚的那一天。
设:排序后第i件商品的利润是 a[i].p，过期天数是a[i].d。
计算第I号商品可以最晚卖出的日期，从过期天数a[i].d 往前查,排除那些已经卖过商品的日期后的最晚的那一天。
直接模拟会超时。怎样更快找到最晚可卖日期？并查集。
不断往前找的过程，很像并查集中不断向上找祖宗的过程。
起初我们把所有日期抽象为一个集合，集合的祖宗（也可以说是集合的代表元素） 。
我们把最晚售卖日期当成把每个集合的祖宗，同时安排个0天的集合，这个集合的祖宗是0，若是有某个商品查到的祖宗是0，表示它这个商品已经没法卖了。
并查集中并的部分：
当某个商品的保质期是d，我们计算出的最晚售卖时间是x，那么我们就将x,x-1 所在集合合并。
含义是，下一次再有保质期是d的商品出现时，它的最晚售卖时间最大可能是x-1，当然x-1 那一天可能也卖过商品了，那它最晚售卖时间就是x-2了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 10005; 4 int n, ans; 5 int f[N]; 6 struct node { 7 int t, val; 8 } a[N]; 9 bool cmp(const node &x, const node &y) { return x.val > y.val; } 10 int find(int x) { 11 if (f[x] < 0) 12 return x; 13 return f[x] = find(f[x]); 14 } 15 int main() { 16 while (cin >> n) { 17 ans = 0; 18 memset(f, -1, sizeof(f)); 19 for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].val, &a[i].t); 20 sort(a + 1, a + 1 + n, cmp); 21 for (int i = 1; i <= n; i++) { 22 int r1 = find(a[i].t); 23 if (r1 > 0) 24 ans += a[i].val, f[r1] = r1 - 1; 25 } 26 printf("%d\n", ans); 27 } 28 return 0; 29 }