一、题目内容
POJ 2431 原题地址
二、题意解释
一辆卡车，初始时，距离终点L，油量为P，在起点到终点途中有n个加油站，每个加油站油量有限，而卡车的油箱容量无限
.
卡车在行车途中，每走一个单位的距离消耗一个单位的油量，给定n个加油站距离终点的距离以及油存储量。
问卡车是否能到达终点，如果可达，最少需要加多少次油，否则输出
-1
.
三、代码及注释
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std
;
int N
,L
,P
;
struct station
{
int a
,b
;
bool operator < (const station
& A
) const{
return a
<A
.a
;
}
}st
[10005];
priority_queue
<int> Q
;
void solve()
{
scanf("%d",&N
);
for(int i
=0; i
<N
; i
++)
{
scanf("%d%d",&st
[i
].a
,&st
[i
].b
);
}
scanf("%d%d",&L
,&P
);
for(int i
=0; i
<N
; i
++)
{
st
[i
].a
=L
-st
[i
].a
;
}
int ans
=0,pos
=0,tank
=P
;
st
[N
].a
=L
;
st
[N
].b
=0;
N
++;
sort(st
,st
+N
);
for(int i
=0; i
<N
; i
++)
{
int t
=st
[i
].a
-pos
;
while(tank
<t
)
{
if(Q
.empty())
{
printf("%d",-1);
return;
}
tank
+=Q
.top();
Q
.pop();
ans
++;
}
tank
-=t
;
Q
.push(st
[i
].b
);
pos
=st
[i
].a
;
}
printf("%d\n",ans
);
}
int main()
{
solve();
return 0;
}
