40017074加油
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
你需要驾驶一辆汽车行驶S个单位的距离。最开始汽车上有P个单位的汽油，汽车每开行1个单位的距离需要消耗1个单位的汽油。如果汽车中途汽油耗尽，将无法继续行驶，因此也就无法到达终点。途中一共有N个加油站，第i个加油站距离起点的距离为Ai个单位距离，第i个加油站你最多可以给汽车加Bi个单位的汽油。假设汽车的邮箱无限大，根据所给的数据，请你计算汽车能否达到终点，如果能到达终点，输出最少需要加油的次数，如果不能到达终点，输出-1。 |
|
输入
|
|
第一行共三个正整数，分别表示N、S和P；第二行有N个正整数分别表示A1，A2，……，An；第三行有N个正整数分别表示B1，B2，……，Bn；每一行的各个数据两两之间用一个空格分隔。
|
|
输出
|
|
按要求输出结果。
|
|
输入示例
|
|
4 25 10
10 14 20 21 10 5 2 4 |
|
输出示例
|
|
2
|
|
其他说明
|
|
数据范围：0<N<=10000，0<S,P<=1000000,0<Ai<=S,0<Bi<=100.
|
咋一看这题就知道是小贪心了吧？
在汽车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站时，就获得了一次在之后的任何时候都可以加Bi单位汽油的权利”，在解决问题上应该也是一样的，而在之后需要加油时，就认为是在之前经过的加油站加的油就可以了。
那么，因为希望到达终点的加油次数少，所以我们把汽车剩余燃料耗到0时再加油看起来是不错的方法。在燃料为0时，找汽车从该阶段起点出发时到燃料为0时的位置内能加油最多的加油站，这是显然的。所以我们可以用队列（prioeity_queue）
在经过加油站i时，往优先队列里加入Bi（也就是说油还够，可以继续行驶）
途中燃料耗尽时，
♢如果优先队列也是空的，说明途中没有加油站，则无法达到终点，输出-1
♢否则取出优先队列最大值，并给汽车加油
注意，priority_queue队列中的top()是取目前队列中的最大值。
切莫忘记将输入数据按加油站从起点到终点的位置顺序(a[i])排序，输因为入时加油站不一定是按位置顺序输入的，我当时就在这磕着了......
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int ans,pos,n,s,p,i;//ans加油次数，pos现在位置
struct GasStation
{
int pos,gas;
GasStation(){
pos=0;
gas=0;
}
bool operator < (const GasStation b)const
{
return pos<b.pos;
}
}a[10001];
int main()
{
priority_queue<int> que;
scanf("%d%d%d",&n,&s,&p);
for(i=0;i<n;i++) scanf("%d",&a[i].pos);
for(i=0;i<n;i++) scanf("%d",&a[i].gas);
sort(a,a+n);
a[n].pos=s,a[n].gas=0,n++;
int tank=p;//油箱中汽油量
for(i=0;i<n;i++){
int d=a[i].pos-pos;//下一个加油站距离现在位置的距离
while(tank-d<0)//不断加油直到油量足够行驶到下一个加油站
{
if(que.empty()){
putchar('-'),putchar('1');
return 0;
}
tank+=que.top();
que.pop();
ans++;
}
tank-=d;
pos=a[i].pos;
que.push(a[i].gas);
}
printf("%d",ans);
return 0;
}
此题解来源于挑战程序设计竞赛（第2版）2.4节Expedition
原题来源于POJ2431