coreBugZJ

此 blog 已棄。

EOJ 1855 Expedition

/*
2

EOJ 1855 Expedition
3

----題意：
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

求最少需要幾次補(bǔ)給可以到達(dá)終點(diǎn)。
12

----輸入：
15

第一行，一個(gè)整數(shù) N；
16

第二行到第N+1行，每行兩個(gè)用空格分開的整數(shù) Di 和 Pi；
17

最后一行，兩個(gè)用空格分開的整數(shù) L 和 P。
18

----輸出：
21

一個(gè)整數(shù)，到達(dá)終點(diǎn)所需的最少補(bǔ)給次數(shù)；若不能到達(dá)終點(diǎn)，輸出整數(shù) -1 。
22

----數(shù)據(jù)范圍：
25

1 <= N <= 10,000；
26

1 <= Pi <= 100
27

1 <= P <= 1,000,000
28

L <= 1,000,000
29

----樣例輸入：
32

4
33

4 4
34

5 2
35

11 5
36

15 10
37

25 10
38

----樣例輸出：
41

2
42

----分析：
45

A.由于車上可以裝載無(wú)限多的燃料，所以不必考慮車上的燃料是否過(guò)多；
46

只需考慮在保證車上燃料夠用的情況下減少補(bǔ)給次數(shù)。
47

B.若車上燃料不夠用，則必須補(bǔ)給；
48

若必須補(bǔ)給卻無(wú)法補(bǔ)給，則無(wú)法到達(dá)終點(diǎn)。
49

C.由于起點(diǎn)到終點(diǎn)的距離已知，且車上所裝載的燃料量已知，且行駛距離與消耗燃料量的關(guān)系已知，
50

所以所需補(bǔ)給的燃料量已知；
51

D.由于起點(diǎn)到終點(diǎn)的距離已知，且車上所裝載的燃料量已知，且行駛距離與消耗燃料量的關(guān)系已知，補(bǔ)給站與終點(diǎn)距離已知，
52

所以可以確定當(dāng)車上有多少燃料時(shí)，可以到哪些補(bǔ)給站獲得補(bǔ)給。
53

E.從某補(bǔ)給站獲得 Pi 單位燃料補(bǔ)給，等價(jià)于卡車在起點(diǎn)處的燃料儲(chǔ)備增加了 Pi 單位且此補(bǔ)給站不存在。
54

----結(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

*/
64

/*********************************************************
67

版本三
68

*/
69

#include <iostream>
70

#include <cstdio>
71

#include <vector>
72

#include <queue>
73

#include <algorithm>
74

using namespace std;
76

typedef pair< int, int > Stop;
78

#define d first
79

#define p second
80

#define L 10009
82

int n;
84

Stop stop[ L ];
85

Stop town;
86

int main() {
88

int i, ans = 0;
89

priority_queue< int > heap;
90

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

sort( stop, stop+n );
98

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

130

using namespace std;
131

132

typedef pair< int, int > Stop;
133

#define d first
134

#define p second
135

136

#define L 10009
137

138

int n;
139

Stop stop[ L ];
140

Stop town;
141

142

int 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

186

using namespace std;
187

188

struct Stop
189

{
190

int d, p;
191

};
192

bool operator<( const Stop &a, const Stop &b ) {
193

return ( a.d < b.d );
194

}
195

196

struct Cmp
197

{
198

bool operator()( const Stop &a, const Stop &b );
199

};
200

bool Cmp::operator()( const Stop &a, const Stop &b ) {
201

return (a.p < b.p);
202

}
203

204

205

#define L 10009
206

207

int n;
208

Stop stop[ L ];
209

Stop town;
210

211

int 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è)

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 微軟2014實(shí)習(xí)生及秋令營(yíng)技術(shù)類職位在線測(cè)試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊(cè)

ACM

AI

LaTeX

安全

編程語(yǔ)言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問(wèn)題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

EOJ 1855 Expedition