http://poj.org/problem?id=2431
题意：驾驶一辆初始油量为P的车，路长L，一路有N个加油站，分别有油量为Ai，距终点Bi，每单位距离消耗1油量，问要到终点最少加油次数，无法到达终点输出-1
分析：当车走到没油的时候，优先选择之前油量最大的加油站加油（可多次），然后继续行驶，如果优先队列为空，则无法到达终点
将加油站距终点的距离转换为距起点的距离，并将终点看成距离L，油量0的加油站
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; #define INF 0x3F3F3F3F typedef pair<int, int> P; int main() { // freopen("input.txt", "r", stdin); int n, l, p; cin >> n; P a[10010]; for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second; cin >> l >> p; for(int i = 0; i < n; i++) a[i].first = l - a[i].first; sort(a, a+n); // for(int i = 0; i < n; i++) // cout << a[i].first << endl; priority_queue<int> pri; a[n].first = l; a[n].second = 0; n++; int ans = 0, pos = 0, tank = p; for(int i = 0; i < n; i++) { int d = a[i].first - pos; while(tank - d < 0) { if(pri.empty()) { cout << -1 << endl; return 0; } else { tank += pri.top(); pri.pop(); ans++; } } tank -= d; pos = a[i].first; pri.push(a[i].second); } cout << ans << endl; return 0; } |