• <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 貪心+堆

            思路:

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

            重復這樣的過程就可以求解了??梢杂枚丫S護加油站中的油量。

            杯具:稍稍修改了一下堆的寫法,結果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 糯米 閱讀(604) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            一级女性全黄久久生活片免费 | 91精品国产91久久| 一本大道久久a久久精品综合| 91精品国产91久久久久久| 久久久久99精品成人片三人毛片 | 国产精品免费福利久久| 九九久久99综合一区二区| 精品久久久久久国产三级| 亚洲一区精品伊人久久伊人 | 欧美亚洲日本久久精品| 一本一本久久a久久综合精品蜜桃 一本一道久久综合狠狠老 | 久久亚洲高清观看| 狠狠色婷婷久久综合频道日韩| 久久精品国产99国产精偷 | 国产精品久久久久久久人人看| 久久久久成人精品无码中文字幕| 麻豆精品久久精品色综合| 色播久久人人爽人人爽人人片AV | 2020国产成人久久精品| 久久精品国产福利国产秒| 亚洲国产欧美国产综合久久| 久久久久久国产a免费观看不卡| 久久综合精品国产二区无码| 一本色道久久88综合日韩精品 | 日韩亚洲欧美久久久www综合网| 亚洲AV无码成人网站久久精品大| 久久久久亚洲?V成人无码| 人人狠狠综合久久亚洲婷婷| aaa级精品久久久国产片| 亚洲愉拍99热成人精品热久久| 中文成人久久久久影院免费观看| 久久99精品久久久久久秒播| 99久久精品免费观看国产| 久久精品国产亚洲综合色| 粉嫩小泬无遮挡久久久久久| 久久久久亚洲AV无码网站| 久久精品国产亚洲av麻豆小说| 久久久久久无码Av成人影院| AAA级久久久精品无码片| 97久久综合精品久久久综合| 久久精品无码专区免费青青|