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

            久久国产色AV免费观看| 婷婷国产天堂久久综合五月| 久久久久亚洲AV无码网站| 99久久无码一区人妻a黑| 久久精品综合一区二区三区| 久久精品国产99久久久古代| 国产精品18久久久久久vr | 久久免费的精品国产V∧| 国产亚洲欧美成人久久片| 亚洲人成无码久久电影网站| AV狠狠色丁香婷婷综合久久 | 国产成人精品久久二区二区| 久久久综合香蕉尹人综合网| 精品久久久久久无码中文字幕一区| 精品久久人人妻人人做精品| 久久久精品人妻一区二区三区四| 国产视频久久| 久久亚洲欧美日本精品| 人人狠狠综合久久88成人| 亚洲欧美久久久久9999| 国产精品成人无码久久久久久| 久久亚洲春色中文字幕久久久| 久久99热这里只频精品6| 国产精品成人精品久久久 | 少妇无套内谢久久久久| 97久久久久人妻精品专区| 99精品国产免费久久久久久下载| 久久高清一级毛片| 国产成人久久久精品二区三区| 国产高潮国产高潮久久久| 久久久婷婷五月亚洲97号色| 狠狠色丁香久久婷婷综合| 久久人妻无码中文字幕| 久久九九久精品国产免费直播| 中文字幕久久亚洲一区| 久久亚洲日韩看片无码| 久久久久久久波多野结衣高潮| 99久久精品国产一区二区 | 国内高清久久久久久| 久久人妻AV中文字幕| 亚洲国产精品成人AV无码久久综合影院|