青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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第一行,一個整數(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.由于起點到終點的距離已知,且車上所裝載的燃料量已知,且行駛距離與消耗燃料量的關系已知,
 50        所以所需補給的燃料量已知;
 51D.由于起點到終點的距離已知,且車上所裝載的燃料量已知,且行駛距離與消耗燃料量的關系已知,補給站與終點距離已知,
 52        所以可以確定當車上有多少燃料時,可以到哪些補給站獲得補給。
 53E.從某補給站獲得 Pi 單位燃料補給,等價于卡車在起點處的燃料儲備增加了 Pi 單位 且 此補給站不存在。
 54
 55
 56----結(jié)論:
 57貪心算法。
 58若卡車在起點處的燃料儲備不足以到達終點,則從其可以到達的補給站中挑選補給量最大的站點獲得補給,
 59獲得補給的方式為 卡車在起點處的燃料儲備增加 Pi 單位并刪除該補給站。
 60重復執(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< intint >  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 閱讀(387) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm課內(nèi)作業(yè)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美视频四区| 亚洲深夜激情| 夜色激情一区二区| 亚洲永久字幕| 国产欧美日本| 美女日韩欧美| 欧美午夜剧场| 久久精品国产综合| 欧美18av| 久久国产精品久久w女人spa| 午夜精品久久久久久久99黑人| 黄色日韩精品| av成人免费在线| 怡红院精品视频在线观看极品| 亚洲国产精品悠悠久久琪琪 | 亚洲午夜激情免费视频| 亚洲高清资源| 久久aⅴ国产欧美74aaa| 欧美一区二区啪啪| 香港久久久电影| 亚洲国产日韩在线| 亚洲精品欧美专区| 悠悠资源网久久精品| 久久精品一区蜜桃臀影院| 亚洲天堂激情| 一本色道久久综合狠狠躁篇的优点| 欧美激情视频一区二区三区不卡| 欧美一级黄色录像| 亚洲精品资源美女情侣酒店| 亚洲无亚洲人成网站77777| 亚洲精品视频免费| 国产精品久久影院| 欧美韩国日本一区| 国产麻豆一精品一av一免费| 亚洲国产综合在线看不卡| 国产精品亚洲综合久久| 亚洲日本乱码在线观看| 尤物精品在线| 欧美一区二视频| 欧美ed2k| 亚洲曰本av电影| 国产精品一区二区视频| 中日韩美女免费视频网址在线观看| 亚洲第一在线视频| 欧美日韩国产另类不卡| 亚洲深夜福利视频| 久久久久久久久久久久久久一区 | 久久综合九色综合欧美就去吻| 亚洲视频精选| 国产精品天天看| 老司机免费视频一区二区| 亚洲人成在线播放| 亚洲欧美经典视频| 伊人成综合网伊人222| 欧美高清日韩| 亚洲精品久久7777| 欧美一区二区三区视频免费| 在线观看日韩av电影| 国产精品色在线| 国内精品久久久久伊人av| 免费看亚洲片| 欧美日韩国产丝袜另类| 中文久久精品| 亚洲黄一区二区三区| 欧美在线观看一区二区三区| 久久精品视频亚洲| 中文网丁香综合网| 亚洲高清电影| 亚洲电影有码| 亚洲欧美日韩在线高清直播| 欧美日产国产成人免费图片| 亚洲精品在线视频观看| 亚洲视频精品| 国产老肥熟一区二区三区| 亚洲男女自偷自拍图片另类| 欧美在线资源| 99精品视频一区| 亚洲福利在线看| 亚洲麻豆av| 在线视频一区观看| 亚洲一区二区三区免费在线观看 | 尹人成人综合网| 国产亚洲午夜高清国产拍精品| 欧美三级午夜理伦三级中文幕 | 一区二区欧美亚洲| 鲁大师影院一区二区三区| 久久久久国产免费免费| 久久女同精品一区二区| 欧美成人精品在线| 亚洲国产成人av在线| 亚洲精品视频免费在线观看| 亚洲美女尤物影院| 亚洲免费视频网站| 久久久噜噜噜久久狠狠50岁| 男人插女人欧美| 国产精品视区| 国产中文一区二区三区| 亚洲欧美成人网| 亚洲人成毛片在线播放| 另类激情亚洲| 亚洲视频在线看| 亚洲摸下面视频| 国产精品欧美精品| 欧美日韩精品中文字幕| 蜜臀91精品一区二区三区| 欧美精品日韩| 国产一区二区三区久久久久久久久| 中文亚洲视频在线| 欧美成人免费va影院高清| av不卡在线看| 99国内精品| 永久免费精品影视网站| 麻豆91精品91久久久的内涵| 亚洲精品免费一区二区三区| 国产真实久久| 国产精品一国产精品k频道56| 欧美a级片网站| 久久丁香综合五月国产三级网站| 91久久线看在观草草青青| 亚洲天堂网在线观看| 亚洲一区二区三区免费观看| 欧美成人乱码一区二区三区| 亚洲国产精品va在线观看黑人| 久久av资源网站| 亚洲欧美日韩国产一区二区| 欧美午夜大胆人体| 久久久亚洲人| 久久成人人人人精品欧| 亚洲国产精品电影| 亚洲国产mv| 欧美色区777第一页| 一区二区三区欧美激情| 亚洲一区三区视频在线观看| 国产一区二区中文| 老司机67194精品线观看| 欧美一区二区私人影院日本 | 欧美大尺度在线| 欧美在线高清视频| 亚洲精品国产精品国自产观看| 亚洲一级片在线看| 欧美日韩精品免费观看视频完整| 亚洲永久免费av| 久久久久久一区二区三区| 亚洲激情小视频| 亚洲天堂av电影| 亚洲综合色噜噜狠狠| 久久久久免费视频| 蜜臀av性久久久久蜜臀aⅴ| 亚洲黄色天堂| 欧美系列一区| 亚洲一区二区三区中文字幕| 亚洲娇小video精品| 欧美日韩精品三区| 久久久噜噜噜久久久| 欧美日韩在线免费| 新67194成人永久网站| 亚洲一级高清| 久久久水蜜桃| 91久久亚洲| 亚洲美女黄网| 国产精品进线69影院| 一区二区三区在线免费观看| 亚洲第一天堂无码专区| 91久久亚洲| 亚洲欧美成人| 久久一区亚洲| 亚洲日本免费电影| 亚洲专区一二三| 久久福利资源站| 国产美女精品视频| 亚洲欧美日韩天堂一区二区| 亚洲男人的天堂在线aⅴ视频| 欧美日韩在线免费观看| 国产欧美一区二区色老头| 日韩午夜剧场| 亚洲视频一区在线观看| 国产精品亚洲片夜色在线| 亚洲女人天堂av| 亚洲国产免费看| 亚洲综合电影一区二区三区| 久久亚洲综合色一区二区三区| 亚洲国产一区二区视频 | 久久久成人网| 亚洲国产日日夜夜| 99精品国产99久久久久久福利| 亚洲欧美激情一区二区| 久久艳片www.17c.com| 一本一本久久a久久精品牛牛影视| 欧美一区1区三区3区公司| 美日韩精品免费观看视频| 国产一区二区三区黄视频| 夜夜嗨av一区二区三区四区| 久久蜜臀精品av| 亚洲综合社区| 国产精品免费视频xxxx| 宅男精品视频| 久久综合一区二区| 久久aⅴ国产欧美74aaa| 日韩亚洲视频在线| 亚洲精品小视频在线观看|