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





            
	    
    




            






            

				

            


    
    







            
	   
	



久久综合综合久久综合|
国产精品热久久毛片|
欧美无乱码久久久免费午夜一区二区三区中文字幕|
久久久久精品国产亚洲AV无码|
99久久国产主播综合精品|
国产∨亚洲V天堂无码久久久|
久久精品国内一区二区三区|
91久久成人免费|
精品久久久久久久久久中文字幕|
久久婷婷人人澡人人爽人人爱|
中文精品久久久久人妻|
囯产精品久久久久久久久蜜桃|
色狠狠久久AV五月综合|
久久国产精品国产自线拍免费|
久久国产精品一区二区|
一级a性色生活片久久无|
色诱久久久久综合网ywww
|
久久精品人人做人人妻人人玩
|
久久久久久国产精品无码超碰|
久久超碰97人人做人人爱|
国产精品久久久久久搜索|
狠狠精品久久久无码中文字幕|
久久人人爽人人爽人人片AV麻烦|
国产精品久久久久久久久免费|
噜噜噜色噜噜噜久久|
国产日韩欧美久久|
91麻豆国产精品91久久久|
狠狠色丁香久久婷婷综合五月
|
久久婷婷人人澡人人|
嫩草伊人久久精品少妇AV|
久久久久亚洲精品无码网址|
99久久99久久精品免费看蜜桃|
国产精品久久久久久久app|
999久久久免费国产精品播放|
国产成人精品免费久久久久|
国产精品99久久久精品无码
|
久久久久亚洲国产|
狠狠人妻久久久久久综合|
99麻豆久久久国产精品免费|
精品伊人久久大线蕉色首页|
久久久久亚洲国产|