POJ 1456 Supermarket (贪心+并查集优化)

Description

A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=Σx∈Sellpx. An optimal selling schedule is a schedule with a maximum profit. 
For example, consider the products Prod={a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell={d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80. 

Write a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set of products. 

Input

A set of products starts with an integer 0 <= n <= 10000, which is the number of products in the set, and continues with n pairs pi di of integers, 1 <= pi <= 10000 and 1 <= di <= 10000, that designate the profit and the selling deadline of the i-th product. White spaces can occur freely in input. Input data terminate with an end of file and are guaranteed correct.

Output

For each set of products, the program prints on the standard output the profit of an optimal selling schedule for the set. Each result is printed from the beginning of a separate line.

Sample Input

4 50 2 10 1 20 2 30 1 7 20 1 2 1 10 3 100 2 8 2 5 20 50 10

Sample Output

80 185

  有n件商品需要卖，每件商品由(p，t)描述。其中p表示该商品被卖出可获得的利润，t表示该商品被卖出的截止时间。时间从1开始计时，每件商品被卖出的话需要占用1个时间单位。如果某件商品的t=3，那么该商品最多只能在时间1，时间2或时间3 这3个时间点上卖。

        现在的问题是：对于给定的所有商品，我们如何安排每个时间点卖的商品能获得最大利润。输出最大利润即可。

以前用贪心做过两次，这次发现可以使用并查集优化，复杂度起码降低了一半。

  当我们处理第i个商品的时候，我们正常来说应该是从i的截止时间往前找，看看有没有空闲时间点来放商品i。这样查找的过程比较慢。

        这里我们用并查集来做些优化，即对于时间点t来说，如果t时间点空闲，那么fa[t]==-1。 我们用findset(t)查找可行时间点时直接就可以返回t(因为t本来就可行)。如果t时间点不空闲，那么我们令fa[t]==t-1。我们用findset(t)查找可行时间点时返回的(不一定是t-1，如果t-1被占用，返回的就不是t-1。否则返回t-1)是从t-1时间点开始递归查找的结果。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 0x3f3f3f3f;
const int MAXN=10000+100;
struct product
{
    int v,t;
    bool operator < (const product &b)const
    {
        return v>b.v;//价值越大排名越前
    }
} pro[MAXN];
int time[MAXN];//time[i]=x表示在时间点i上放了价值x的商品准备卖
int F[MAXN];
int findset(int i)
{
    if(F[i]==-1)return i;
    return F[i]=findset(F[i]);
}
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        int ans=0;//最大利益
        memset(time,0,sizeof(time));
        memset(F,-1,sizeof(F));
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&pro[i].v,&pro[i].t);
        }
        sort(pro,pro+n);
        for(int i=0; i<n; i++)
        {
            int t = findset(pro[i].t);//找到pro[i].t这个时间往前的第一个空闲时间点
            if(t>0)
            {
                F[t]=t-1;
                ans += pro[i].v;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}