• <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 閱讀(145) 評論(0)  編輯 收藏 引用 所屬分類: data struct

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国内精品久久久久久久影视麻豆| 97久久精品国产精品青草| 精品综合久久久久久88小说| 国产精品午夜久久| 思思久久好好热精品国产| 亚洲第一极品精品无码久久| 久久精品亚洲一区二区三区浴池| 亚洲国产精品久久久久婷婷老年| 久久国产热这里只有精品| 日韩乱码人妻无码中文字幕久久| 中文字幕成人精品久久不卡 | 久久亚洲国产午夜精品理论片| 久久99热精品| 色综合久久中文字幕无码| 久久99精品国产99久久6| 中文字幕日本人妻久久久免费| 久久综合久久久| 久久国产精品无码一区二区三区| 久久久精品久久久久久 | 久久精品国产亚洲AV无码麻豆| 91精品婷婷国产综合久久| 乱亲女H秽乱长久久久| 色婷婷综合久久久久中文字幕| 国产69精品久久久久777| 伊人久久大香线蕉av一区| 久久一区二区免费播放| 久久青草国产手机看片福利盒子| 99久久这里只精品国产免费 | 老色鬼久久亚洲AV综合| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 亚洲国产精品18久久久久久| 久久婷婷国产剧情内射白浆| 精品国产综合区久久久久久 | 久久精品?ⅴ无码中文字幕| 99久久精品国产高清一区二区| 久久久久se色偷偷亚洲精品av| 少妇久久久久久被弄到高潮 | 久久永久免费人妻精品下载| 免费精品久久天干天干| 中文精品99久久国产 | 久久精品国产久精国产果冻传媒|