• <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一輛卡車從起點駛向終點，每行進一單位距離，消耗一單位燃料。
              7起點距終點有 L 單位距離，車上有 P 單位燃料。
              8中途有 N 個補給站，第 i 個補給站距終點有 Di 單位距離，可提供的補給為 Pi 單位燃料。
              9假設(shè)車上可以裝載無限多的燃料。
             10
             11求最少需要幾次補給可以到達終點。
             12
             13
             14----輸入：
             15第一行，一個整數(shù) N；
             16第二行到第N+1行，每行兩個用空格分開的整數(shù) Di 和 Pi；
             17最后一行，兩個用空格分開的整數(shù) L 和 P。
             18
             19
             20----輸出：
             21一個整數(shù)，到達終點所需的最少補給次數(shù)；若不能到達終點，輸出整數(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.由于車上可以裝載無限多的燃料，所以不必考慮車上的燃料是否過多；
             46只需考慮在保證車上燃料夠用的情況下減少補給次數(shù)。
             47B.若車上燃料不夠用，則必須補給；
             48若必須補給卻無法補給，則無法到達終點。
             49C.由于起點到終點的距離已知，且車上所裝載的燃料量已知，且行駛距離與消耗燃料量的關(guān)系已知，
             50        所以所需補給的燃料量已知；
             51D.由于起點到終點的距離已知，且車上所裝載的燃料量已知，且行駛距離與消耗燃料量的關(guān)系已知，補給站與終點距離已知，
             52        所以可以確定當車上有多少燃料時，可以到哪些補給站獲得補給。
             53E.從某補給站獲得 Pi 單位燃料補給，等價于卡車在起點處的燃料儲備增加了 Pi 單位 且 此補給站不存在。
             54
             55
             56----結(jié)論：
             57貪心算法。
             58若卡車在起點處的燃料儲備不足以到達終點，則從其可以到達的補給站中挑選補給量最大的站點獲得補給，
             59獲得補給的方式為 卡車在起點處的燃料儲備增加 Pi 單位并刪除該補給站。
             60重復(fù)執(zhí)行以上步驟，直到燃料儲備充足或無法獲得補給。
             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) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



国产精品久久久久9999高清|
久久精品无码一区二区app|
久久久久这里只有精品|
日日狠狠久久偷偷色综合免费|
青青草国产97免久久费观看|
伊人久久综合成人网|
99国产精品久久久久久久成人热|
国产成人无码精品久久久久免费|
国产精品亚洲美女久久久|
国产69精品久久久久观看软件|
久久久国产精品亚洲一区|
久久久久亚洲精品中文字幕|
99国产欧美久久久精品蜜芽|
欧美国产成人久久精品|
狠狠久久亚洲欧美专区|
思思久久99热只有频精品66|
国产精品久久久久影院嫩草
|
无码国内精品久久人妻蜜桃|
秋霞久久国产精品电影院|
伊人久久久AV老熟妇色|
爱做久久久久久|
avtt天堂网久久精品|
久久久久亚洲av成人网人人软件
|
波多野结衣中文字幕久久|
久久人人爽人人爽人人av东京热
|
国产69精品久久久久观看软件|
成人亚洲欧美久久久久|
久久Av无码精品人妻系列
|
亚洲国产小视频精品久久久三级|
国产一区二区三区久久精品|
一本久久a久久精品亚洲|
日产久久强奸免费的看|
久久久久久青草大香综合精品|
久久99精品国产麻豆宅宅|
久久精品国产亚洲av日韩|
日韩久久久久久中文人妻|
色综合久久久久综合体桃花网|
久久久久久久97|
久久久久无码精品国产|
国产精品久久久久久久|
国内精品伊人久久久久影院对白|