题干的大概意思就是说：
你开着车从距离目的地L公里远的地方向前出发，此时油箱内有P升油,每走1公里消耗1升油。沿途有几个加油站，并给出了它们的位置以及加油站的剩余油量(也就是你最多可以在这里加多少升油)
请你计算能否到达目的地,如果能到达输出最少加油多少次，不能到达输出-1
思路:每次循环记录下一加油站与当前位置的距离，判断当前剩余油量能否到达，如果能到达就把该加油站的油量放入一个堆数组中，如果不能到达，从堆数组中（堆数组的特点:最上面的一定是最大或者最小值）取出堆顶元素加给当前油量，同时记录加油次数的变量+1
为什么这样做呢:可以这样想,由于油箱没有限制，但我肯定只能在我能走到的加油站才能加油，那么我每次肯定选油量最大的加油站加。我思路可能说的不是很清晰
举个栗子: 假如我走过了四个加油站，把这四个加油站的油量存放在堆数组的1，2，3，4位置处，
这时我发现我不能到达第五个加油站了，我肯定在前四个加油站中选一个油量最大的加油站加，这样能让我到达的更远，有可能我加上最大的就可以直接到终点了,而在其他地方加油可能最多只能过第五个加油站，那我只加一次油就可以了，而如果选择其他地方则至少要加两次油。要注意的地方就是如何在新元素入堆和旧元素出堆时仍然保持堆的有序性。
AC代码：
#include <stdio.h>
#define MAX 10002
int Q[MAX+1],L,P; //数组Q表示最大堆 Q[0]用来存储当前堆存取的 数的数量 Q[1]开始存数
typedef struct loc
{int locate;int num;
}Locate;
Locate p[MAX];
void Insert(int Heap[],int X) //堆中插入新元素堆依然有序
{ int par,i=++Heap[0]; //插入X 后 Heap[0]+1 while(i>1) //直到i不是根节点 { par=(i/2); //父节点为par if(Heap[par]>=X) break; //如果父节点满足最大堆的特性 则插入当前的位置即可 Heap[i]=Heap[par]; //否则调整堆 即位置上移 i=par; } Heap[i]=X; //插入新节点
}
int Delmax(int Heap[]) //取堆中最大值然后删除该元素堆依然有序
{ int i=1,root=Heap[1],R,L,X=Heap[Heap[0]--]; //X记录当前末尾节点 root为根 即为最大值 while(i*2<=Heap[0]) { L=i*2;R=L+1; //Left Right 记录左右节点 if(R<=Heap[0]&&Heap[R]>Heap[L]) //比较两个子节点的值的大小 L=R; //记录子节点中较大的那个if(Heap[L]<=X) break; //如果所有的位置已经调整好 跳出循环 Heap[i]=Heap[L]; //否则继续调整堆 i=L; } Heap[i]=X; return root;
}
void quick_sort(Locate p[],int left,int right) //快速排序
{int i=left,j=right;int pivot=p[(i+j)/2].locate;Locate temp;while (i<=j){while(p[i].locate<pivot) i++;while(p[j].locate>pivot) j--;if(i<=j){temp=p[i];p[i]=p[j];p[j]=temp;i++;j--;}}if(i<right) quick_sort(p,i,right);if(left<j) quick_sort(p,left,j);
}
void Init(int N) //初始化输入
{for(int i=1;i<=N;i++){scanf("%d %d",&p[i].locate,&p[i].num);}scanf("%d %d",&L,&P);for(int i=1;i<=N;i++){p[i].locate=L-p[i].locate;}p[N+1].locate=L,p[N+1].num=0;quick_sort(p,1,N+1);return ;
}
int solve(int n)
{int flag=0;int i,local=0,oil=0,dis; //local是当前位置,oil是目前油量,dis是到下一站的距离oil=P;for(i=1;i<=n+1;i++){dis=p[i].locate-local; //到下一站需要的距离while (oil<dis){if(!Q[0]) //加油站的堆不空{return -1;}oil+=Delmax(Q);flag++;}oil-=dis;local=p[i].locate;Insert(Q,p[i].num); //该加油站的油量入堆}return flag;
}
int main()
{ int N; scanf("%d",&N);Init(N);printf("%d\n",solve(N));return 0;
}
//poj 2431看了其他人的做法，大多都是贪心＋优先级队列，但我没学过c++语言，这篇文章参考了看到的一个大佬的方法，用堆来代替优先级队列。
对我个人的思考就是，堆是不是也能在某种程度上代替优先级队列，本题中用的是int型，假如按照结构体中的某个元素的优先级来排序,是不是也可以这样做，只需要把int换成自己定义的数据类型即可。