• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 195,  comments - 30,  trackbacks - 0

            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

             

            Hint

            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.


            #include<iostream>
            #include<cstdlib>
            using namespace std;
            #define MAX 10001
            #define min(a,b) ((a)<(b) ? (a) : (b))
            int father[MAX];
            int p[MAX];
            int result[MAX];
            struct job{
                 int value;
                 int T;
              }JOB[MAX];
            bool operator <(job job1,job job2)
             {
              if(job1.value>job2.value)
              return true;
              else
              return false;
             } 
             int find(int x)  //·µ»ØµÚ£Ø½ÚµãËùÊô¼¯ºÏµÄ¸ù½áµã
              {
            int px=x;
            while(p[px]>=0)
               px=p[px];
            int tmp;
            while(p[x]>=0)//ӦΪ³õֵΪ¸º
            {
               tmp=p[x];
               p[x]=px;
               x=tmp;
            }
            return px;
            }

               void UNION(int x,int y)
            {
            x=find(x);
            y=find(y);
            if(x==y)
               return ;
            int tmp=p[x]+p[y];
            if(p[x]>p[y])
            {
               p[y]=tmp;
               p[x]=y;
            }
            else
            {
               p[x]=tmp;
               p[y]=x;
            }
            }
             
              int main()
              {
              freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
              int num,temp=0;
              while(cin>>num)
              {
              memset(result,0,num);
              int i,l,j,k=0;
              for( i=0;i<num;i++)
              {
               cin>>JOB[i].value>>JOB[i].T;
               father[i]=i;
               p[i]=-1;
              }
              sort(JOB,JOB+num);
              for(i=0;i<num;i++)
              {
               j=find(min(JOB[i].T,num-1));//
               if(father[j]!=0)
                   {
                 k++;
                 result[k]=i;
                    l=find(father[j]-1);
                    UNION(l,j);
                    father[j]=father[l];
                }
              }
              i=0;
              for(j=1;j<=k;j++)
              { 
               i+=JOB[result[j]].value;}
                cout<<i<<endl;
               }

              //system("PAUSE");
              return   0;
              }
            對著課本寫得,自己都看不怎么懂。

            posted on 2009-07-02 13:11 luis 閱讀(518) 評論(0)  編輯 收藏 引用 所屬分類: 貪心*二分
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久无码人妻一区二区三区午夜| 久久精品国产亚洲AV不卡| 精品免费久久久久久久| 青青草原综合久久大伊人| 伊人久久大香线焦AV综合影院 | 精品久久久久久无码中文字幕| 91久久精品国产91性色也| 久久亚洲av无码精品浪潮| 97精品伊人久久久大香线蕉| 久久99热精品| 久久精品国产AV一区二区三区| 国产精品久久久福利| 久久亚洲2019中文字幕| 国产精品福利一区二区久久| 深夜久久AAAAA级毛片免费看| 久久久久久久97| 久久久久人妻一区精品| 国产韩国精品一区二区三区久久| 久久se精品一区二区影院| 久久青青草原亚洲av无码app | 97超级碰碰碰碰久久久久| 久久久午夜精品福利内容| 久久久久久久综合日本亚洲| 国产一区二区久久久| 成人午夜精品久久久久久久小说 | 久久久青草久久久青草| 狠狠色婷婷久久一区二区| 欧美一级久久久久久久大片| 久久综合久久综合久久综合| 久久精品天天中文字幕人妻| 久久天天躁夜夜躁狠狠| 污污内射久久一区二区欧美日韩 | 久久天天躁狠狠躁夜夜不卡| 久久久久久无码国产精品中文字幕 | 97久久国产亚洲精品超碰热| 亚洲国产精品无码久久| 久久精品国产久精国产果冻传媒| 久久福利资源国产精品999| 久久久久亚洲AV无码专区首JN| 午夜视频久久久久一区| 午夜精品久久久久|