来源:书《挑战程序设计竞赛》85页
题目
一群牛抢了一辆卡车,冒险到丛林深处探险。这些牛是相当可怜的司机,不幸的是,它们撞上了一块石头,刺穿了卡车的油箱。现在卡车每行驶一单位距离就会泄漏一单位燃料。
为了修理卡车,奶牛们需要沿着一条长长的、蜿蜒的道路开车到最近的城镇(距离不超过100万个单位)。在这条道路上,在城镇和卡车当前位置之间,有N (1 <= N <= 10,000)个加油站,奶牛可以在那里停下来获得额外的燃料(1..每站100个单位)。
丛林对人类来说是一个危险的地方,对牛来说尤其危险。因此,奶牛想要在去城镇的路上尽可能少地停下来加油。幸运的是,他们卡车上的油箱容量如此之大,以至于实际上没有限制它所能容纳的燃油量。卡车目前离城镇有L单位的距离,有P单位的燃料(1 <= P <= 1,000,000)。
确定到达城镇所需的最少站点数,或者奶牛根本无法到达城镇(输出为-1)。
样例输入:
4
4 4
5 2
11 5
15 10
25 10
样例输出
2
样例输入输出说明
第1行:单个整数N
第2行到第N+1:每一行包含两个用空格分隔的整数,描述一个加油站:第一个整数是从城镇到加油站的距离;第二个是该站点的可用燃油量。
第N+2行:两个用空格分隔的整数,L和P
输入详细信息:
卡车离城镇25个单位;这辆卡车有10单位燃料。沿着公路,在距离城镇4、5、11和15处有4个加油站(所以这些最初距离卡车21、20、14和10处)。这些燃料停止可以分别提供多达4、2、5和10单位的燃料。
输出详细信息:
行驶10个单位,停下来获得10个单位的燃料,再行驶4个单位,停下来获得5个单位的燃料,然后行驶到城镇。
思路:
此题可以改变一下思路,还有油的时候先一直开,每到一个加油站就把它的所有油先保存好。当油量为0时,使用一个当前记录下的可用的最大的油量。而这个使用的油量,可以等价为我们到达此对应加油站时加的最大的油量。
这样就是 再油量为0的时候,选择经过的某个加油站的油进行加油。
而我们每次拿油量最多的,这样可以使得使用的加油站最少。
所以可以用一个大根堆的优先队列,存好经过的每个加油站的油量。
代码实现:
# include <iostream>
# include <algorithm>
# include <queue>
using namespace std;
typedef pair<int,int> PII; //<i,j>, i存入距离起始位置的距离,j存加汽油量
const int N = 10010;
PII add[N]; //存的就是最大能加的量
priority_queue<int> temp; //大根堆
int n,l,p;
int main()
{
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d %d",&add[i].first,&add[i].second);
}
scanf("%d %d",&l,&p);
for(int i = 1 ; i <= n ; i++)
{
add[i].first = l - add[i].first; //注意,此题输入的时候,输入的是加油站离终点的距离,而不是加油站与起点之间的距离
}
sort(add + 1 , add + n + 1); //将加油站按照从小到大的距离排序
int res = p; //先将当前油用完
int total = 0;
int i = 1;
for( ; i <= n ; i++) //将当前可以走到的汽油站的汽油加入优先队列中,为后面找最大的汽油量做准备
{
if(add[i].first <= res)
{
temp.push(add[i].second);
}
else
{
break;
}
}
while(temp.size())
{
if(res >= l) //队列不空时,如果到达了终点,则可以退出了
{
break;
}
int t = temp.top(); //如果没到,则将最大汽油量加进来
total++;
temp.pop(); //堆中最大的值删除
res += t; // 加了汽油后最大到的距离
for(; i <= n ; i++)
{
if(add[i].first <= res)
{
temp.push(add[i].second);
}
else
{
break;
}
}
}
if(res >= l)
{
printf("%d\n",total);
}
else
{
printf("-1\n");
}
return 0;
}