POJ 2431 - Expedition

http://poj.org/problem?id=2431

概要

壊れた燃料タンクを直すために距離が L だけ離れている街へ向かう．

タンクには最初 P だけ燃料があるが，単位距離進む毎に1単位分の燃料を失う．

街までの道には N 個の燃料補給所がある． i 番目の補給所は街から X[i] の位置にあり，そこで F[i] の燃料を補給することができる． タンクに保存できる燃料の量に上限は無い．

街まで進むために必要な最小の燃料補給の回数を答える．

ただし，どのように進んでも街まで辿り着けない場合は -1 を答える．

制約

• L <= 1000000
• 1 <= N <= 10000
• 1 <= F[i] <= 100
• 1 <= P <= 1000000

解法

今ある燃料で行ける(行けた)補給所の中から，最も補給量が多いところを貪欲に選んでいけばよい．

priority_queue を使うとこれを簡単に実装できる．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 #include <functional>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int main()
 9 {
10   int N;
11   scanf("%d", &N);
12   vector<pair<int,int> > fuels(N);
13   for (int i = 0; i < N; i++) {
14     scanf("%d%d", &fuels[i].first, &fuels[i].second);
15   }
16   int L, P;
17   scanf("%d%d", &L, &P);
18   sort(fuels.begin(), fuels.end(), greater<pair<int,int> >());
19 
20   int ans = 0;
21   vector<pair<int,int> >::const_iterator it = fuels.begin();
22   const vector<pair<int,int> >::const_iterator end = fuels.end();
23   int rest = L - P;
24   priority_queue<int> q;
25   while (rest > 0) {
26     while (it != end && it->first >= rest) {
27       q.push(it->second);
28       ++it;
29     }
30     if (q.empty()) {
31       ans = -1;
32       break;
33     } else {
34       rest -= q.top();
35       q.pop();
36       ++ans;
37     }
38   }
39   printf("%d\n", ans);
40 
41   return 0;
42 }