http://poj.org/problem?id=2431
题意:
你需要驾驶一辆卡车行驶L单位距离。最开始时,卡车上有P单位的汽油。卡车每开1单位距离需要消耗1单位的汽油。如果在途中车上的汽油耗尽,卡车就无法继续前行,因而无法到达终点。在途中一共有N个加油站。第i个加油站在距离终点Ai单位距离的地方,最多可以给卡车加Bi单位汽油。假设卡车的燃料箱的容量是无限大的,无论加多少油都没有问题。那么请问卡车是否能到达终点?如果可以,最少需要加多少次油?如果可以到达终点,输出最少的加油次数,否则输出-1。
分析:
看当前油量能否到达下一个加油站
能:则把下一个加油站的油量B加入到优先队列里。同时更新一下剩余油量和当前位置。
不能:则取出优先队列中最大的元素,用来给卡车加油。 如果优先队列为空,则无法到达终点。
code:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; struct node { int fuel, dist; bool operator <(const node& t) const { return dist>t.dist; } } a[10005]; int main() { int n, i, fuels, ans, L, P, pos, d; scanf("%d",&n); priority_queue<int, vector<int>, less<int> > q; for(i=0; i<n; i++) { scanf("%d%d",&a[i].dist, &a[i].fuel); } sort(a,a+n);//从大到小排序 scanf("%d%d",&L,&P); a[n].dist = 0; for(i=0; i<=n; i++) { a[i].dist =L-a[i].dist; } // for(i=0; i<=n; i++) printf("%d %d\n",a[i].dist, a[i].fuel); fuels = P; ans = 0; pos = 0; for(i=0; i<=n; i++) { d = a[i].dist-pos; while(fuels-d<0) { if(q.empty()) { printf("-1\n"); return 0; } fuels += q.top(); q.pop(); ans++; } fuels -= d; pos = a[i].dist; q.push(a[i].fuel); } printf("%d\n",ans); return 0; }