【传送门：BZOJ1747】
简要题意：
奶牛们驾驶着一辆卡车，在丛林中探险。卡车每前进1 公里会消耗1 升汽油，奶牛必须赶在汽油 用尽之前返回城市。奶牛目前距离城市有L 公里，但邮箱里只有P 升汽油了。 好在回去的路上存在N 个汽油补给点，第i 个补给点距离终点有Xi 公里，可以补给Ui 升汽油。 这辆卡车的油箱非常大，多少油都能装得下。丛林是个危险的地方，除非必要，奶牛们是不太希望停 车加油的。请算出奶牛至少要加几次油才能到达终点，或者告诉它们无论怎么样都到不了目的地。
输入格式：
• 第一行：单个整数N，1 ≤ N ≤ 10000
• 第二行到第N + 1 行：第i + 1 行有两个整数Xi 和Ui，1 ≤ Xi ≤ L; 1 ≤ Ui ≤ 100
• 第N + 2 行：两个整数L 和P，1 ≤ P ≤ L ≤ 10^6
输出格式：
• 单个整数：为达到终点最少停车加油的次数，如果无法到达终点，输出−1
样例输入：
4
4 4
5 2
11 5
15 10
25 10
样例输出：
2
样例解释：
前进10公里，加10升油，再前进4公里，加5升油，就能直接开到终点了
题解：
一眼DP题，结果被D飞，数据范围惊人
发现加油不用花费，所以就想到一旦需要加油就将加油站的油都拿走，就想到了贪心
用优先队列来储存，一个加油站一个加油站的前进，一旦不够油就取堆顶的值，每当经过一个加油站就当作一份补给放进优先队列里，其实这种操作很像游戏里面的HP药水，先拿大的磕，再磕小的
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> using namespace std; priority_queue<int> q; struct node { int x,u; }a[11000]; int cmp(const void *xx,const void *yy) { node n1=*(node *)xx; node n2=*(node *)yy; if(n1.x>n2.x) return -1; if(n1.x<n2.x) return 1; return 0; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].u); qsort(a+1,n,sizeof(node),cmp); int L,p; scanf("%d%d",&L,&p); a[0].x=L; a[n+1].x=0; int ans=0; for(int i=1;i<=n+1;i++) { while(p<a[i-1].x-a[i].x) { if(q.empty()==true){printf("-1 ");return 0;} p+=q.top(); q.pop(); ans++; } p-=a[i-1].x-a[i].x; q.push(a[i].u); } printf("%d ",ans); return 0; }