• <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 閱讀(730) 評論(0)  編輯 收藏 引用 所屬分類: Standing Programs
            你是第 free hit counter 位訪客




            <2025年8月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(4)

            隨筆分類(54)

            隨筆檔案(52)

            文章檔案(1)

            ACM/ICPC

            技術綜合

            最新隨筆

            搜索

            •  

            積分與排名

            • 積分 - 64180
            • 排名 - 357

            最新評論

            閱讀排行榜

            評論排行榜

            午夜精品久久久久久毛片| 99精品国产99久久久久久97 | 久久天天躁狠狠躁夜夜不卡| 中文精品久久久久人妻| 亚洲精品午夜国产va久久| 久久久久国产精品人妻| 情人伊人久久综合亚洲| 热99RE久久精品这里都是精品免费| 久久久久久国产精品免费无码| 欧美综合天天夜夜久久| 精品久久久久久久久免费影院| 久久久久亚洲av无码专区喷水| 久久精品无码一区二区三区日韩 | 久久久老熟女一区二区三区| 超级碰久久免费公开视频| 久久无码高潮喷水| 久久国产福利免费| 久久综合狠狠色综合伊人| 一本久久a久久精品亚洲| 久久综合九色综合欧美就去吻| 国内精品久久人妻互换| 久久精品国产色蜜蜜麻豆| 久久久99精品一区二区| 91秦先生久久久久久久| 97久久国产亚洲精品超碰热| 色综合久久无码中文字幕| 亚洲伊人久久成综合人影院| 国产激情久久久久影院小草| 69久久夜色精品国产69| 精品久久久久久无码专区不卡| 亚洲AV日韩精品久久久久久| 久久婷婷国产剧情内射白浆| 久久久久久久综合狠狠综合| 久久综合视频网| yy6080久久| 无码人妻少妇久久中文字幕蜜桃| 亚洲国产精品无码久久一线| 久久ww精品w免费人成| 国产精品久久久久…| 亚洲国产成人久久精品动漫| 久久精品无码av|