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


            May the force be with you!
            posts - 52,  comments - 33,  trackbacks - 0

                    
                  這個題目原來比賽WA了,后來一直沒有做出來,最近比賽又遇上,郁悶地想了好幾天,我在網上沒有找到正確答案,昨天向tank請教,終于知道了算法,今天AC了,寫出來吧……

            題目來源:ICPC2003廣州賽區
            題目網址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1771

            算法:二分+貪心

                     計算出一個需要可行的時間,然后用二分法枚舉可能的解,判斷解的可行性時用貪心策略:對每個人,檢驗他能在規定時間內到達,如果不能到達,則需要多停靠一次,解不等式找出能停靠的最高樓層(證明就算了,說明一下:因為要求的是每個人都能在指定時間能到達,所以貪心選擇使得電梯的停靠層往上同時滿足當前的人能在規定時間能到達即可,這樣再往上的人離停靠的樓層就近一些……)。
                    我的代碼風格很好(自己暫時這么認為:-)),還不清楚就看代碼了……

            類似題目:POJ1744http://acm.pku.edu.cn/JudgeOnline/problem?id=1744
                                WOJ1297  Elevator Stopping Plan



              1/*****************************************
              2Date:2007-10-29
              3Author:littlekid
              4
              52844442    LittleKid    1771    Accepted    216K    0MS    G++    2063B    2007-10-29 17:12:02
              6
              7**********************************************/

              8
              9
             10# include <stdio.h>
             11# include <string.h>
             12
             13# define N 33
             14
             15int n;
             16int tar[N];
             17
             18int ans;
             19int stop;
             20int station[N],result[N];
             21
             22int MIN(int a,int b)
             23{
             24    return a>b?b:a;
             25}

             26
             27void init()
             28{
             29    for (int i = 1;i <= n; i ++)
             30    {
             31        scanf("%d",&tar[i]);
             32    }

             33}

             34
             35bool isOK(int time)
             36{
             37    int t_st=1,t_ti=0;
             38    int tmp;
             39    stop=0;
             40    for (int i=1;i<=n;i++)
             41    {
             42       // if (canGet(i,t_st,t_ti)) continue ;
             43        if (tar[i] <= t_st) continue;
             44        tmp = t_ti+(tar[i]-t_st)*20;
             45        if (tmp <= time) continue ;
             46        
             47        //getStop();
             48        if (t_st == 1)
             49        {
             50            tmp = time - t_ti + (4*t_st+20*tar[i]);
             51        }

             52        else
             53        {
             54            tmp = time - (t_ti+10+ (4*t_st+20*tar[i]);
             55        }

             56        tmp /= 24;
             57        if (tmp<tar[i]) return false;
             58        if (t_st==1)
             59        {
             60            t_ti+= (tmp-t_st)*4;
             61        }

             62        else
             63        {
             64            t_ti += 10+(tmp-t_st)*4;
             65        }

             66        t_st = tmp;
             67        stop++; station[stop]=t_st;
             68       // printf("-->%d\n",t_st);
             69    }

             70    
             71    return true;
             72}

             73
             74void solve()
             75{
             76    ans = tar[n]*4+20*(tar[n]-tar[1]);
             77    result[0]=1; result[1]=tar[n];
             78    
             79    int low=0,up=ans-1,mid;
             80    while (low<up)
             81    {
             82        mid = (low+up)/2;
             83        if (isOK(mid))
             84        {
             85            {
             86                result[0]=stop;
             87                for (int i=1;i<=stop;i++)
             88                {
             89                    result[i] = station[i];
             90                }

             91                ans = mid;
             92            }

             93            up = mid;
             94        }

             95        else
             96        {
             97            low = mid+1;
             98        }

             99    }

            100}

            101
            102void output()
            103{
            104    printf("%d\n%d",ans,result[0]);
            105    for (int i=1;i<=result[0];i++)
            106    {
            107        printf(" %d",result[i]);
            108    }

            109    printf("\n");
            110}

            111
            112int main()
            113{
            114    while (1)
            115    {
            116        scanf("%d",&n);
            117        if (n == 0break;
            118        init();
            119        solve();
            120        output();
            121    }

            122    return 0;
            123}
            posted on 2007-10-29 21:35 R2 閱讀(719) 評論(0)  編輯 收藏 引用 所屬分類: Standing Programs
            你是第 free hit counter 位訪客




            <2007年10月>
            30123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            常用鏈接

            留言簿(4)

            隨筆分類(54)

            隨筆檔案(52)

            文章檔案(1)

            ACM/ICPC

            技術綜合

            最新隨筆

            搜索

            •  

            積分與排名

            • 積分 - 63692
            • 排名 - 358

            最新評論

            閱讀排行榜

            評論排行榜

            欧美大香线蕉线伊人久久| 中文字幕亚洲综合久久2| 国内精品伊人久久久影院| 欧美亚洲国产精品久久久久| 久久亚洲国产最新网站| 国内精品久久久久久久97牛牛| 国产精品久久久久久久久鸭| 久久99精品久久久久久齐齐| 99久久这里只精品国产免费| 99国产精品久久久久久久成人热| 久久人妻少妇嫩草AV蜜桃| 热re99久久6国产精品免费| 99久久精品免费看国产一区二区三区 | 日韩久久无码免费毛片软件| 久久久久久亚洲精品成人 | 亚洲国产精品成人久久蜜臀| 精品久久久久久成人AV| 一本一道久久a久久精品综合| 日韩精品久久久久久| 无码国内精品久久人妻蜜桃| 日本加勒比久久精品| 欧美精品一区二区精品久久| 欧美va久久久噜噜噜久久| 免费久久人人爽人人爽av| 欧美性大战久久久久久| 国产激情久久久久影院| 久久久久四虎国产精品| 久久精品国产99久久无毒不卡| 中文字幕亚洲综合久久菠萝蜜| 久久人搡人人玩人妻精品首页| 国内精品欧美久久精品| 国产高清美女一级a毛片久久w| 伊人久久综在合线亚洲2019| 97久久精品无码一区二区天美| 无码人妻精品一区二区三区久久久 | 一本综合久久国产二区| 无夜精品久久久久久| 久久性精品| 国产偷久久久精品专区| 亚洲国产另类久久久精品小说 | 奇米影视7777久久精品人人爽|