POJ 2431 Expedition （优先队列+贪心）

题目大意：

你需要驾驶一辆卡车行驶L距离，最开始时，卡车上有P的汽油，卡车每开1单位距离需要消耗1单位的汽油。在途中有N个加油站，第i个加油站在距离起点Ai距离的地方，最多可以给卡车加Bi汽油，假设卡车的容量是无限大的，无论加多少油都没有问题。求卡车到达终点需要加的最少的汽油。

思路：

可以换个思路：在到达加油站i时，就获得了一次在之后的任何时候都可以加Bi单位汽油的权利。而在之后需要加油的时候，就认为是在之前经过的加油站加的油就可以。

所以，我们每次没油的时候，选择一个加油站（之前经过的）最大可加油的进行加油（故用堆/优先队列维护）。

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=10000+10; struct point { int dis; int val; bool operator<(const point&a)const{ return val < a.val; } }a[MAXN]; bool cmp(const point &a,const point &b){ return a.dis
     
       q; int cnt=0; for(int i=1;i<=n;i++) { int d=a[i].dis-a[i-1].dis; while(d > p) { if(q.empty()) { printf(-1 ); goto end; } p+=q.top().val; q.pop(); cnt++; } p-=d; q.push(a[i]); } printf(%d ,cnt); end:; } return 0; }