题目传送门

　　传送点I

　　传送点II

题目大意

　　有$n$个商品可以销售。每个商品销售会获得一个利润，但也有一个时间限制。每个商品需要1天的时间销售，一天也只能销售一件商品。问最大获利。

 /**

  * poj

  * Problem#1456

  * Accepted

  * Time: 47ms

  * Memory: 768k

  */

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 typedef bool boolean;

 typedef class Product {

     public:

         int profit;

         int deadline;

         Product() {    }

         boolean operator < (Product b) const {

             return profit > b.profit;

         }

 }Product;

 const int N = 1e4 + ;

 int n, res;

 int pre[N];

 Product *ps;

 boolean vis[N]; 

 inline boolean init() {

     if (scanf("%d", &n) == EOF)

         return false;

     res = ;

     ps = new Product[(n + )];

     for (int i = ; i <= n; i++)

         scanf("%d%d", &ps[i].profit, &ps[i].deadline);

     return true;

 }

 int findPre(int p) {

     if (!p)    return ;

     if (!vis[p]) {

         vis[p] = true;

         return p;

     }

     return pre[p] = findPre(pre[p]);

 }

 inline void solve() {

     sort(ps + , ps + n + );

     memset(vis, false, sizeof(vis));

     for (int i = ; i <= ; i++)

         pre[i] = i - ;

     for (int i = ; i <= n; i++) {

         int p = findPre(ps[i].deadline);

         if (p)

             res += ps[i].profit;

     }

     printf("%d\n", res);

     delete[] ps;

 }

 int main() {

     while (init())

         solve();

     return ;

 }