• <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>

            pku 3483 Loan Scheduling 有期限的單位時間任務最大獲益問題,貪心+并查集

            題意簡要的說就是N件任務,每件任務i有期限di和收益pi,每個時刻能同時做n個任務,求最大獲益。
            貪心策略是這樣的:先對任務按照收益排序,然后盡可能地往靠近期限的地方丟,這里用到并查集來優化,如果某個時刻已經被占用n次了,則將其與前面一個格子合并,具體細節注意下就可以了
             1 # include <cstdio>
             2 # include <algorithm>
             3 using namespace std;
             4 struct node
             5 {
             6      int p,d;
             7 }data[10005];
             8 bool cmp(const node &a,const node &b)
             9 {
            10      return a.p>b.p;
            11 }
            12 int set[10005];
            13 int co[10005];
            14 int find(int pos)
            15 {
            16    if(set[pos]==pos)
            17      return pos;
            18    else return set[pos]=find(set[pos]);
            19 }
            20 int num,l;
            21 int main()
            22 {
            23      while(scanf("%d%d",&num,&l)!=EOF)
            24      {
            25         for(int i=0;i<num;i++)
            26            scanf("%d%d",&data[i].p,&data[i].d);
            27         for(int i=0;i<=10000;i++)
            28           set[i]=i,co[i]=l;
            29         sort(data,data+num,cmp);
            30         int total=0;
            31         for(int i=0;i<num;i++)
            32         {
            33            if(co[find(data[i].d)]==0continue;
            34            else
            35            {
            36                co[find(data[i].d)]--;
            37                total+=data[i].p;
            38                if(!co[find(data[i].d)])
            39                {
            40                   for(int j=data[i].d;j>=0;j--)
            41                   {
            42                       if(co[find(j)])
            43                       {
            44                          set[find(data[i].d)]=find(j);
            45                          break;
            46                       }
            47                   }
            48                }    
            49            }
            50         }
            51         printf("%d\n",total);
            52      } 
            53      return 0;
            54 }
            55 


            posted on 2010-11-07 02:11 yzhw 閱讀(144) 評論(0)  編輯 收藏 引用 所屬分類: data struct

            <2011年7月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            婷婷五月深深久久精品| 日本强好片久久久久久AAA| 国产精品久久久久无码av| 久久亚洲日韩精品一区二区三区| 色88久久久久高潮综合影院 | 国产99精品久久| 91精品婷婷国产综合久久| 亚洲国产天堂久久综合| 一本一本久久a久久综合精品蜜桃 一本一道久久综合狠狠老 | 久久精品国产亚洲av日韩| 久久久久久免费一区二区三区| 亚洲狠狠综合久久| 偷窥少妇久久久久久久久| 免费国产99久久久香蕉| 性做久久久久久久久浪潮| 麻豆AV一区二区三区久久| 久久久久久久久久免免费精品| 国产精品久久久久jk制服| 无码8090精品久久一区| 久久综合九色综合欧美狠狠| 囯产精品久久久久久久久蜜桃 | 国产999精品久久久久久| 综合久久精品色| 色综合久久综精品| 亚洲午夜久久久久久久久电影网| 国产免费久久久久久无码| 久久亚洲AV成人出白浆无码国产| 亚洲伊人久久综合影院| 久久r热这里有精品视频| 久久强奷乱码老熟女网站| 久久久久九九精品影院| 久久精品国产亚洲7777| 狠狠色综合久久久久尤物| 久久91精品久久91综合| 久久久中文字幕| 狠狠色丁香久久婷婷综| 久久精品国产亚洲av高清漫画| 久久精品免费一区二区| 久久婷婷午色综合夜啪| 久久这里有精品| 亚洲中文字幕无码久久2020|