POJ-1456-Supermarket-白红宇

POJ-1456-Supermarket

阅读量：6496 次

发布时间：2019-06-24

本文共 1178 字，大约阅读时间需要 3 分钟。

链接：https://vjudge.net/problem/POJ-1456#author=shleodai

题意：

超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.

每天只能卖一个商品.

现在你要让超市获得最大的利润.

(原题说明过于抽象)

思路：

贪心加并查集，先将所有物品以价格排序。

之后选物品时，先用并查集，往前查第一个没用过的天。

同时将使用的天合并。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;const int MAXN = 10000+10;struct Node{ int _value; int _day; bool operator < (const Node & that)const { return this->_value > that._value; }}node[MAXN];int Father[MAXN];int Get_F(int x){ if (Father[x] == -1) return x; Father[x] = Get_F(Father[x]); return Father[x];}int main(){ int n; while (cin >> n) { memset(Father,-1, sizeof(Father)); for (int i = 1;i<=n;i++) cin >> node[i]._value >> node[i]._day; sort(node+1,node+1+n); /* for (int i = 1;i<=n;i++) cout << node[i]._value << ' ' << node[i]._day << endl; */ int sum = 0; for (int i = 1;i<=n;i++) { int td = Get_F(node[i]._day); if (td > 0) { sum += node[i]._value; Father[td] = td-1; } } cout << sum << endl; } return 0;}