POJ 1456 Supermarket

题意：商场卖东西，每种商品有两个属性，一种是价格pi，另一种是保质期di，每种商品只能在天数<=di的时候卖出。每天只能卖一种商品，问最多能卖出价格之和为多少的商品。(n <= 10^4，di <= 10^4，pi <= 10^4)

解法：贪心。首先对所有商品排个序，然后从价格高到价格低，考虑每一件物品能否被卖出去，若能则卖，不能则考虑下一件，直到遍历完所有商品。

　　　考虑某件商品x的时候，判断di天是否要卖商品，如果那天不卖则di天卖，否则考虑di - 1天卖，再否则考虑di - 2天卖。。。如果直到第1天都不能卖出该件商品，则认为该商品不能卖出。

　　　这个方法如果用hash来记录，就会是O(n^2)的复杂度，不能接受。但是可以考虑用并查集优化。对某个节点x，其父亲节点f[x]表示小于等于x的天数中，最大的可以卖出商品的日子。比如，第2，3，5，7天要卖出商品，则f[1] = 1，f[2] = 1，f[3] = 1，f[4] = 4，f[5] = 4，f[6] = 6，f[7] = 6，f[8] = 8。

tag:greedy, 并查集, good

 /*

  * Author:  Plumrain

  * Created Time:  2013-11-26 11:33

  * File Name: G-POJ-1456.cpp

  */

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <utility>

 using namespace std;

 typedef pair<int, int> pii;

 int n, f[];

 pii a[];

 bool cmp(pii a, pii b)

 {

     return a.first > b.first;

 }

 int find(int x)

 {

     if (x != f[x]) f[x] = find(f[x]);

     return f[x];

 }

 int gao()

 {

     int sum = ;

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

         int t1 = a[i].first, t2 = a[i].second;

         int x = find(t2);

         if (x > ){

             sum += t1;

             f[x] = x - ;

         }

     }

     return sum;

 }

 int main()

 {

     while (scanf ("%d", &n) != EOF){

         int maxd = ;

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

             scanf ("%d%d", &a[i].first, &a[i].second);

             maxd = max(maxd, a[i].second);

         }

         sort(a, a+n, cmp);

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

             f[i] = i;

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

     }

     return ;

 }

巴特西

POJ 1456 Supermarket

最新文章

热门文章