coreBugZJ

此 blog 已棄。

EOJ 1855 Expedition

/*
2

EOJ 1855 Expedition
3

----題意：
6

一輛卡車從起點駛向終點，每行進一單位距離，消耗一單位燃料。
7

起點距終點有 L 單位距離，車上有 P 單位燃料。
8

中途有 N 個補給站，第 i 個補給站距終點有 Di 單位距離，可提供的補給為 Pi 單位燃料。
9

假設車上可以裝載無限多的燃料。
10

求最少需要幾次補給可以到達終點。
12

----輸入：
15

第一行，一個整數 N；
16

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

最后一行，兩個用空格分開的整數 L 和 P。
18

----輸出：
21

一個整數，到達終點所需的最少補給次數；若不能到達終點，輸出整數 -1 。
22

----數據范圍：
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.由于車上可以裝載無限多的燃料，所以不必考慮車上的燃料是否過多；
46

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

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

若必須補給卻無法補給，則無法到達終點。
49

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

所以所需補給的燃料量已知；
51

D.由于起點到終點的距離已知，且車上所裝載的燃料量已知，且行駛距離與消耗燃料量的關系已知，補給站與終點距離已知，
52

所以可以確定當車上有多少燃料時，可以到哪些補給站獲得補給。
53

E.從某補給站獲得 Pi 單位燃料補給，等價于卡車在起點處的燃料儲備增加了 Pi 單位且此補給站不存在。
54

----結論：
57

貪心算法。
58

若卡車在起點處的燃料儲備不足以到達終點，則從其可以到達的補給站中挑選補給量最大的站點獲得補給，
59

獲得補給的方式為卡車在起點處的燃料儲備增加 Pi 單位并刪除該補給站。
60

重復執行以上步驟，直到燃料儲備充足或無法獲得補給。
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 閱讀(393) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、課內作業

只有注冊用戶登錄后才能發表評論。


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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

EOJ 1855 Expedition