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

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 1855 Expedition
		
            
		
              1/*
              2EOJ 1855 Expedition
              3
              4
              5----題意：
              6一輛卡車從起點(diǎn)駛向終點(diǎn)，每行進(jìn)一單位距離，消耗一單位燃料。
              7起點(diǎn)距終點(diǎn)有 L 單位距離，車上有 P 單位燃料。
              8中途有 N 個(gè)補(bǔ)給站，第 i 個(gè)補(bǔ)給站距終點(diǎn)有 Di 單位距離，可提供的補(bǔ)給為 Pi 單位燃料。
              9假設(shè)車上可以裝載無(wú)限多的燃料。
             10
             11求最少需要幾次補(bǔ)給可以到達(dá)終點(diǎn)。
             12
             13
             14----輸入：
             15第一行，一個(gè)整數(shù) N；
             16第二行到第N+1行，每行兩個(gè)用空格分開的整數(shù) Di 和 Pi；
             17最后一行，兩個(gè)用空格分開的整數(shù) L 和 P。
             18
             19
             20----輸出：
             21一個(gè)整數(shù)，到達(dá)終點(diǎn)所需的最少補(bǔ)給次數(shù)；若不能到達(dá)終點(diǎn)，輸出整數(shù) -1 。
             22
             23
             24----數(shù)據(jù)范圍：
             251 <= N  <= 10,000；
             261 <= Pi <= 100
             271 <= P  <= 1,000,000
             28     L  <= 1,000,000
             29
             30
             31----樣例輸入：
             324
             334 4
             345 2
             3511 5
             3615 10
             3725 10
             38
             39
             40----樣例輸出：
             412
             42
             43
             44----分析：
             45A.由于車上可以裝載無(wú)限多的燃料，所以不必考慮車上的燃料是否過多；
             46只需考慮在保證車上燃料夠用的情況下減少補(bǔ)給次數(shù)。
             47B.若車上燃料不夠用，則必須補(bǔ)給；
             48若必須補(bǔ)給卻無(wú)法補(bǔ)給，則無(wú)法到達(dá)終點(diǎn)。
             49C.由于起點(diǎn)到終點(diǎn)的距離已知，且車上所裝載的燃料量已知，且行駛距離與消耗燃料量的關(guān)系已知，
             50        所以所需補(bǔ)給的燃料量已知；
             51D.由于起點(diǎn)到終點(diǎn)的距離已知，且車上所裝載的燃料量已知，且行駛距離與消耗燃料量的關(guān)系已知，補(bǔ)給站與終點(diǎn)距離已知，
             52        所以可以確定當(dāng)車上有多少燃料時(shí)，可以到哪些補(bǔ)給站獲得補(bǔ)給。
             53E.從某補(bǔ)給站獲得 Pi 單位燃料補(bǔ)給，等價(jià)于卡車在起點(diǎn)處的燃料儲(chǔ)備增加了 Pi 單位 且 此補(bǔ)給站不存在。
             54
             55
             56----結(jié)論：
             57貪心算法。
             58若卡車在起點(diǎn)處的燃料儲(chǔ)備不足以到達(dá)終點(diǎn)，則從其可以到達(dá)的補(bǔ)給站中挑選補(bǔ)給量最大的站點(diǎn)獲得補(bǔ)給，
             59獲得補(bǔ)給的方式為 卡車在起點(diǎn)處的燃料儲(chǔ)備增加 Pi 單位并刪除該補(bǔ)給站。
             60重復(fù)執(zhí)行以上步驟，直到燃料儲(chǔ)備充足或無(wú)法獲得補(bǔ)給。
             61
             62
             63*/
             64
             65
             66/*********************************************************
             67版本三
             68*/
             69#include <iostream>
             70#include <cstdio>
             71#include <vector>
             72#include <queue>
             73#include <algorithm>
             74
             75using namespace std;
             76
             77typedef  pair< int, int >  Stop;
             78#define  d first
             79#define  p second
             80
             81#define  L  10009
             82
             83int   n;
             84Stop  stop[ L ];
             85Stop  town;
             86
             87int main() {
             88        int i, ans = 0;
             89        priority_queue< int >  heap;
             90
             91        scanf( "%d", &n );
             92        for ( i = 0; i < n; ++i ) {
             93                scanf( "%d%d", &(stop[ i ].d), &(stop[ i ].p) );
             94        }
             95        scanf( "%d%d", &(town.d), &(town.p) );
             96
             97        sort( stop, stop+n );
             98
             99        i = n - 1;
            100        while ( (i >= 0) && (town.d - stop[ i ].d <= town.p) ) {
            101                heap.push( stop[ i ].p );
            102                --i;
            103        }
            104
            105        while ( (town.d > town.p) && (! heap.empty()) ) {
            106                ++ans;
            107                town.p += heap.top();
            108                heap.pop();
            109
            110                while ( (i >= 0) && (town.d - stop[ i ].d <= town.p) ) {
            111                        heap.push( stop[ i ].p );
            112                        --i;
            113                }
            114        }
            115
            116        printf( "%d\n", ( (town.d <= town.p) ? ans : (-1) ) );
            117        return 0;
            118}
            119
            120
            121/*********************************************************
            122版本二
            123*/
            124/*
            125#include <iostream>
            126#include <vector>
            127#include <queue>
            128#include <algorithm>
            129
            130using namespace std;
            131
            132typedef  pair< int, int >  Stop;
            133#define  d first
            134#define  p second
            135
            136#define  L  10009
            137
            138int   n;
            139Stop  stop[ L ];
            140Stop  town;
            141
            142int main() {
            143        int i, ans = 0;
            144        priority_queue< int >  heap;
            145
            146        cin >> n;
            147        for ( i = 0; i < n; ++i ) {
            148                cin >> stop[ i ].d >> stop[ i ].p;
            149        }
            150        cin >> town.d >> town.p;
            151
            152        sort( stop, stop+n );
            153
            154        i = n - 1;
            155        while ( (i >= 0) && (town.d - stop[ i ].d <= town.p) ) {
            156                heap.push( stop[ i ].p );
            157                --i;
            158        }
            159
            160        while ( (town.d > town.p) && (! heap.empty()) ) {
            161                ++ans;
            162                town.p += heap.top();
            163                heap.pop();
            164
            165                while ( (i >= 0) && (town.d - stop[ i ].d <= town.p) ) {
            166                        heap.push( stop[ i ].p );
            167                        --i;
            168                }
            169        }
            170
            171        cout << ( (town.d <= town.p) ? ans : (-1) ) << endl;
            172        return 0;
            173}
            174*/
            175
            176
            177/*********************************************************
            178版本一
            179*/
            180/*
            181#include <iostream>
            182#include <vector>
            183#include <queue>
            184#include <algorithm>
            185
            186using namespace std;
            187
            188struct  Stop
            189{
            190        int d, p;
            191};
            192bool operator<( const Stop &a, const Stop &b ) {
            193        return ( a.d < b.d );
            194}
            195
            196struct  Cmp
            197{
            198        bool operator()( const Stop &a, const Stop &b );
            199};
            200bool Cmp::operator()( const Stop &a, const Stop &b ) {
            201        return (a.p < b.p);
            202}
            203
            204
            205#define  L  10009
            206
            207int   n;
            208Stop  stop[ L ];
            209Stop  town;
            210
            211int main() {
            212        int i, ans = 0;
            213        priority_queue< Stop, vector< Stop >, Cmp >  heap;
            214
            215        cin >> n;
            216        for ( i = 0; i < n; ++i ) {
            217                cin >> stop[ i ].d >> stop[ i ].p;
            218        }
            219        cin >> town.d >> town.p;
            220
            221        sort( stop, stop+n );
            222
            223        i = n - 1;
            224        while ( (i >= 0) && (town.d - stop[ i ].d <= town.p) ) {
            225                heap.push( stop[ i ] );
            226                --i;
            227        }
            228
            229        while ( (town.d > town.p) && (! heap.empty()) ) {
            230                ++ans;
            231                town.p += heap.top().p;
            232                heap.pop();
            233
            234                while ( (i >= 0) && (town.d - stop[ i ].d <= town.p) ) {
            235                        heap.push( stop[ i ] );
            236                        --i;
            237                }
            238        }
            239
            240        cout << ( (town.d <= town.p) ? ans : (-1) ) << endl;
            241        return 0;
            242}
            243*/
            244
            
		
            
			posted on 2012-03-04 22:35 coreBugZJ 閱讀(385) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久综合色区|
国产成人AV综合久久|
久久精品国产乱子伦|
久久精品蜜芽亚洲国产AV|
99久久国产综合精品网成人影院|
久久激情亚洲精品无码?V|
久久99精品久久久大学生|
国产精品久久久久天天影视|
久久精品国产只有精品66|
色婷婷久久综合中文久久蜜桃av|
久久av高潮av无码av喷吹|
亚洲精品乱码久久久久久蜜桃不卡
|
久久99亚洲综合精品首页|
影音先锋女人AV鲁色资源网久久
|
亚洲欧美日韩中文久久
|
日韩中文久久|
伊人色综合久久|
东京热TOKYO综合久久精品|
日本欧美国产精品第一页久久|
国产综合久久久久|
久久青青草视频|
久久精品18|
国内精品久久久久久久涩爱|
久久久亚洲欧洲日产国码aⅴ|
九九精品久久久久久噜噜|
久久国产成人精品国产成人亚洲|
精品久久久久久中文字幕人妻最新|
区亚洲欧美一级久久精品亚洲精品成人网久久久久
|
久久99国产精品久久久|
久久人人妻人人爽人人爽|
久久99热这里只有精品国产|
久久高清一级毛片|
久久久久国产精品嫩草影院|
国产综合精品久久亚洲|
国产精品女同一区二区久久|
99久久www免费人成精品|
欧美日韩中文字幕久久伊人|
青青青国产精品国产精品久久久久
|
久久国产乱子伦精品免费强|
久久精品www人人爽人人|
精品久久久久久无码专区|