poj-1456

Myth丶恋晨 2022-06-01 08:28 119阅读 0赞

<table style="font-family:&quot;Microsoft YaHei&quot;"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-family:Arial,Helvetica,sans-serif; font-size:18pt; font-weight:bold; color:blue">
      Supermarket 
    </div> 
    <div style="text-align:center; font-family:Arial,Helvetica,sans-serif; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;14241</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;6447</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="text-align:left; font-family:Arial,Helvetica,sans-serif; font-size:18pt; font-weight:bold; color:blue"> Description</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt">
      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)=Σ 
     <sub>x∈Sell</sub>px. An optimal selling schedule is a schedule with a maximum profit. 
     <br> 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.&nbsp; 
     <br>  
     <img src="http://poj.org/images/1456_1.jpg" alt="">  
     <br> 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.&nbsp; 
     <br> 
    </div> <p style="text-align:left; font-family:Arial,Helvetica,sans-serif; font-size:18pt; font-weight:bold; color:blue"> Input</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt">
      A set of products starts with an integer 0 &lt;= n &lt;= 10000, which is the number of products in the set, and continues with n pairs pi di of integers, 1 &lt;= pi &lt;= 10000 and 1 &lt;= di &lt;= 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. 
    </div> <p style="text-align:left; font-family:Arial,Helvetica,sans-serif; font-size:18pt; font-weight:bold; color:blue"> Output</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt">
      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. 
    </div> <p style="text-align:left; font-family:Arial,Helvetica,sans-serif; font-size:18pt; font-weight:bold; color:blue"> Sample Input</p> <pre style="font-family:&quot;Courier New&quot;,Courier,monospace; font-size:12pt">4  50 2  10 1   20 2   30 1

7  20 1   2 1   10 3  100 2   8 2
   5 20  50 10
</pre> <p style="text-align:left; font-family:Arial,Helvetica,sans-serif; font-size:18pt; font-weight:bold; color:blue"> Sample Output</p> <pre style="font-family:&quot;Courier New&quot;,Courier,monospace; font-size:12pt">80
185</pre> <p style="text-align:left; font-family:Arial,Helvetica,sans-serif; font-size:18pt; font-weight:bold; color:blue"> Hint</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt">
      The sample input contains two product sets. The first set encodes the products from table 1. The second set is for 7 products. The profit of an optimal schedule for these products is 185. 
    </div> <p style="text-align:left; font-family:Arial,Helvetica,sans-serif; font-size:18pt; font-weight:bold; color:blue"> Source</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=Southeastern+Europe+2003" rel="nofollow">Southeastern Europe 2003</a> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

题目大意：

题意：超市有n个商品，每个商品有利润p和保质期d，每天卖一种商品问怎么卖才能使利润最大，求出最大利润。

思路：贪心，先按照商品利润从大到小排序，选出利润大的开始卖，卖的时间就在保质期d当天，若当天已经有商品在卖了，就从d往前推 看哪一天可以卖该商品。

代码1：

贪心做法：

#include<queue>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int fu[10010],zi[10010],c[10010],mark[10010];
    struct node
    {
        int x,y;
    } chanpin[10010];
    int cmp(node a,node b)
    {
        return a.x>b.x;
    }
    int main()
    {
        int n,m;
        while(scanf("%d",&n)!=EOF)
        {
            int i,j,ans=0;
            for(i=0; i<n; i++)
            {
                scanf("%d%d",&chanpin[i].x,&chanpin[i].y);
            }
            memset(mark,0,sizeof(mark));
            sort(chanpin,chanpin+n,cmp);
            for(i=0; i<n; i++)
            {
               for(j=chanpin[i].y;j>0;j--)
               {
                   if(!mark[j])
                   {
                       ans+=chanpin[i].x;
                       mark[j]=1;
                       break;
                   }
               }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

代码2：

并查集做法：

#include<queue>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int fu[10010],zi[10010],c[10010],mark[10010];
    struct node
    {
        int x,y;
    } chanpin[10010];
    int cmp(node a,node b)
    {
        return a.x>b.x;
    }
    void shuru()
    {
        int i;
        for(i=0; i<10010; i++)
            fu[i]=i;
    }
    int findroot(int x)
    {
        if(x!=fu[x])
            fu[x]=findroot(fu[x]);
        return fu[x];
    }
    int main()
    {
        int n,m;
        while(scanf("%d",&n)!=EOF)
        {
            int i,j,ans=0,sum=0;
            shuru();
            for(i=0; i<n; i++)
            {
                scanf("%d%d",&chanpin[i].x,&chanpin[i].y);
            }
            memset(mark,0,sizeof(mark));
            sort(chanpin,chanpin+n,cmp);
            for(i=0; i<n; i++)
            {
                ans=findroot(fu[chanpin[i].y]);
                if(ans>0)
                {
                    sum+=chanpin[i].x;
                    fu[ans]=ans-1;//把该时间的合法时间往前推移1
                }
            }
            printf("%d\n",sum);
        }
        return 0;
    }