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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 2431 Expedition 貪心+堆

            思路:

            有油的時候能走多遠就走多遠,看能否走到目的地。
            如果走不到,就必須要加一次油,途中會遇到很多加油站,一定要選油最多的那個。
            這很容易理解,因為如果你只加這一次,越多當然越好。如果要以后還要加,那能走遠一點選擇也多一點。

            重復這樣的過程就可以求解了。可以用堆維護加油站中的油量。

            杯具:稍稍修改了一下堆的寫法,結果WA兩次。。

            代碼:
            #include <stdio.h>
            #include 
            <stdlib.h>

            #define MAX_N 10032

            struct node {
                
            int x, f;
            }
            ;

            struct node stop[MAX_N];
            int N, L, P;
            int heap[MAX_N], heap_size;

            inline 
            void shift_up(int idx)
            {
                
            int val = heap[idx];
                
            while (idx > 1 && heap[idx/2< val) {
                    heap[idx] 
            = heap[idx/2];
                    idx 
            /= 2;
                }

                heap[idx] 
            = val;
            }


            inline 
            void shift_down(int idx)
            {
                
            int val = heap[idx];
                
            while (1{
                    idx 
            *= 2;
                    
            if (idx > heap_size)
                        
            break;
                    
            if (idx + 1 <= heap_size && heap[idx + 1> heap[idx])
                        idx
            ++;
                    
            if (val >= heap[idx])
                        
            break;
                    heap[idx
            /2= heap[idx];
                }

                heap[idx
            /2= val;
            }


            int cmp(const void *a, const void *b)
            {
                
            return ((struct node *)b)->- ((struct node *)a)->x;
            }


            inline 
            void push(int val)
            {
                heap[
            ++heap_size] = val;
                shift_up(heap_size);
            }


            inline 
            void pop()
            {
                heap[
            1= heap[heap_size--];
                shift_down(
            1);
            }


            int main()
            {
                
            int i, x, t;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d"&N);
                
            for (i = 0; i < N; i++)
                    scanf(
            "%d%d"&stop[i].x, &stop[i].f);
                scanf(
            "%d%d"&L, &P);
                qsort(stop, N, 
            sizeof(stop[0]), cmp);

                push(P);
                x 
            = L;
                i 
            = 0;
                
            for (t = 0; heap_size && x > 0; t++{
                    x 
            -= heap[1];
                    pop();
                    
            while (i < N && x <= stop[i].x)
                        push(stop[i
            ++].f);
                }

                printf(
            "%d\n", x <= 0 ? t - 1 : -1);

                
            return 0;
            }



            posted on 2010-04-13 13:53 糯米 閱讀(603) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            午夜精品久久久久久久无码| 国产午夜免费高清久久影院| 国产精品亚洲美女久久久| 91精品国产91久久久久久蜜臀| 久久91这里精品国产2020| 香蕉久久夜色精品国产2020| 99精品国产99久久久久久97| 久久精品国产亚洲沈樵| 精品人妻伦九区久久AAA片69 | 久久99国产精品成人欧美| 亚洲欧洲中文日韩久久AV乱码| 99久久综合国产精品免费| 99久久免费国产精品热| 国产精品久久久久久久app | 久久久久久亚洲AV无码专区| 青青青青久久精品国产| 久久AV高潮AV无码AV| 亚洲午夜久久久精品影院| 久久精品国产亚洲AV影院| 国产精品久久久天天影视香蕉| 99久久99久久精品国产片果冻| 久久国产精品免费| 久久精品国产精品青草 | 亚洲午夜精品久久久久久人妖| 无码人妻精品一区二区三区久久 | 久久久无码人妻精品无码| 久久强奷乱码老熟女网站| 久久美女人爽女人爽| 影音先锋女人AV鲁色资源网久久| 久久久久久一区国产精品| 91麻豆精品国产91久久久久久| 国产精品无码久久综合| 久久人人爽人人爽人人片av高请| 国产精品一区二区久久精品涩爱 | 热久久最新网站获取| 久久久久国产日韩精品网站 | 亚洲人成无码久久电影网站| 久久久久久亚洲精品无码| 久久久久综合中文字幕| 久久伊人精品青青草原日本| 久久亚洲中文字幕精品一区四|