题目粗心：
已知终点与起点的间隔为D,油箱的最大油量为Cmax,单位汽油可能反对后退Davg。给定N个加油站的单位油价和离终点的间隔C所有加油站都在一条线上)，汽车初始时刻处于终点地位，油箱为空，且能够在任意加油站购买任意量的汽油(前提是不超过油箱容量)，求从终点到起点的最小破费。如果无奈达到起点，则输入可能行驶的最远距离。
算法思路：
此题考查的是贪婪算法的思维，这里次要阐明加油站的抉择策略，并且提供2中不同的实现代码。对于每一个加油站，假如以后加油站为j，汽车能够行驶
的最大间隔为max_dis。咱们首先在从加油站j能够达到的最远加油站(距杭州的间隔小于等于加油站j加上max_dis)之间进行遍历，如果能够找到比加油站j油价低的加油站，那么抉择间隔j最近的加油站为下一站。如果没有，那么找到油价最低的加油站作为下一站。如果从加油站j没有能够达到的加油站，那么阐明没法后退，以后加油站的间隔加上max_dis就是最大行驶间隔.
算法实现1：
应用stations数组存储所有的加油站，这里将起点也作为一个加油站，其油价为0，间隔为D，油价之所以为0，是因为当存在max_dis的范畴蕴含起点的时候得抉择油价比以后加油站j的油价低的加油站，不然间接去起点，所以0能够保障肯定存在这样的加油站。而后依照加油站的间隔从小到大进行排序，对于第一个加油站的间隔不为0的得非凡判断，阐明不可达，间接输入”The maximum travel distance = 0.00″。而后遍历每一个加油站(真正的加油站，所以i<N而不是N+1)，首先找到下一站的地址min_pos，如果min_pos==-1，阐明不存在下一站，输入最长行驶间隔。否则，进行加油，如果以后的加油站j油价较低，那么在以后加油站加满，否则只加恰好到下一站的油。最初更新以后加油站的地位j=min_pos
算法实现2：
相比拟于算法实现1，没有将起点当成是一个加油站，而是进行了非凡解决。这里设置了以后加油站为now,假如在now加满油后,能够来到加油站的最大间隔为tempDis = Cmax*Davg(600),那么间隔杭州的最大间隔为gap = station[now].dis+tempDis。在下一站加油站的选取的实现上也有所区别，这里先取得汽车第一个达不到的加油站为i，那么now+1~i-1的加油站就是所有能够达到的，在now+1~i-1中选出下一站的地位。在now==N-1，也就是达到最初一个加油站的状况在最初一个加油站如果最远行驶中央能够达到起点,就累加跑到起点的油费,如果不能,阐明无奈达到起点,最远距离就是gap,并且让是否跑到起点的标记flag=false;同时如果以后不是最初一个加油站,会呈现一种特判状况，就是以后加油站加满油后能够行驶的最远地位距终点的间隔gap>=D,那么得判断在前面所有的加油站中是否存在比以后now加油站更加便宜的加油站temp，如果有，得先到temp而后再持续判断,如果没有间接达到起点，更新相干信息即可。
留神点：
1、所有的数据除了加油站数目是整型int,其余的都是double。
2、在终点没有加油站得特判，测试点2考查
提交后果：
第一次测试：测试点4谬误。
谬误起因未知，换了一种写法就通过了
对于算法实现1和2都通过PAT的测试
这里同时给上牛客网的测试后果，算法实现1通过了牛客网的测试，算法实现2只通过2个点（(╥╯^╰╥)）
测试用例：
Sample Input:
15 2383 13 10
424238335 0
86 60
49 161
62 1033
90 1279
63 1891
40 311
72 13
11 1945
67 1095
Sample Output:
The maximum travel distance = 506.00AC代码1：
#include <cstdio>
#include <algorithm>
using namespace std;
struct Station{
double price;//汽油单价
double dis;//以后加油站与杭州的间隔
};
bool cmpByDis(Station a,Station b){
return a.dis<b.dis;
}
int main(){
double Cmax,D,Davg;// 油箱容量，全长间隔，每单位汽油行驶的间隔
int N; //加油站个数
scanf("%lf %lf %lf %d",&Cmax,&D,&Davg,&N);
Station stations[N+1];
for (int i = 0; i < N; ++i) {
scanf("%lf %lf",&stations[i].price,&stations[i].dis);
}
stations[N].dis = D;
stations[N].price = 0;
// 依照间隔杭州的间隔进行排序
sort(stations,stations+N,cmpByDis);
// 把起点也看成是一个加油站
// 初始化数据
double total_price = 0;//达到起点的总消耗
double tank_capacity = 0;//以后的油箱油量
double max_dis = Cmax*Davg;//汽车能够行驶的最大间隔
// 首先判断在终点是否有加油站
if(stations[0].dis!=0){
printf("The maximum travel distance = 0.00");
return 0;
}
for (int j = 0; j < N; ) {
// 找到在间隔以后加油站max_dis内的所有加油站中油价比以后加油站低且最近的加油站，如果没有找到油价最低的加油站
int min_pos = -1;
double min_price = 10000000;
for (int i=j+1;i<N+1&&stations[j].dis+max_dis>=stations[i].dis;++i) {
if(min_price>stations[i].price){
// 更新最小油价和地位
min_pos = i;
min_price = stations[i].price;
if(min_price<stations[j].price){
// 找到比以后加油站油价更低的加油站i
break;
}
}
}
if (min_pos==-1){
// 不存在能够达到的加油站
printf("The maximum travel distance = %.2lf",stations[j].dis+max_dis);
return 0;
}
// 将汽车开到min_pos地位的加油站
// 首先计算所须要的油量
double need = (stations[min_pos].dis-stations[j].dis)/Davg;
if (stations[min_pos].price>stations[j].price){
//以后的加油站油价更低，加满油再走
total_price += (Cmax-tank_capacity)*stations[j].price;//更新消耗
tank_capacity = Cmax;//加油结束，更新油量
}else {
// 以后的加油站油价更高，只加恰好到min_pos的油
if(tank_capacity<need){
// 油箱的油有余，须要在以后加油站加油
total_price += (need-tank_capacity)*stations[j].price;//更新消耗
tank_capacity = need;//加油结束，更新油量
}
}
tank_capacity -= need;//行驶结束，更新油量
j = min_pos;//达到目的地，更新加油站地位
}
printf("%.2lf",total_price);
return 0;
}AC代码2：
#include<cstdio>
#include<algorithm>
using namespace std;
struct gasStation{
float price;//油价
float dis;//加油站到杭州的间隔
}station[500];
bool cmp(gasStation g1,gasStation g2){
return g1.dis<g2.dis;
}
int main(){
float Cmax,D,Davg; //汽车油箱的量，杭州到起点城市的间隔，每单元汽油能够跑的间隔
int N;//加油站数目
scanf("%f %f %f %d",&Cmax,&D,&Davg,&N);
for(int i=0;i<N;++i){
scanf("%f %f",&station[i].price,&station[i].dis);
}
sort(station,station+N,cmp);
float cheapest = 0;//跑到起点的起码油钱
bool flag = true;//是否跑到起点
float maxDis = 0;//不能跑到起点的最大间隔
float tempDis = Cmax*Davg;//从以后加油站登程加满油能跑得最大间隔
int now = 0;//最近工夫一次汽车加油的加油站
float CRemain = 0;//油箱残余油量,初始为0
if(station[now].dis!=0){//以后开始的加油站间隔杭州不为0，所以加不了油，无奈发车
printf("The maximum travel distance = 0.00");
return 0;
}
while(now<N){
int CNeed = Cmax-CRemain;//以后汽车所能加油的最大油量
float gap = station[now].dis+tempDis;//假如加满从以后加油站跑得最远的中央间隔杭州的间隔
if(now==N-1){//以后是最初一个加油站,前面没有加油站了，就无奈再遍历，得特判
if(gap<D) {//gap<D，阐明没有跑到最终地位
maxDis = gap;//能跑得最远距离就是gap
flag = false;
}else{//能够跑到起点
cheapest += station[now].price*(D-station[now].dis)/Davg;//累计跑到起点的钱
}
break;
}
if(gap>=D){//从now加满油后能够跑到起点,且以后加油站不是最初一个加油站,得判断在now到最初加油站之间是否有比now更便宜的加油站
int temp;
for(temp=now+1;temp<N;++temp){
if(station[temp].price<station[now].price){
break;
}
}
if(temp!=N){//阐明的确有，不能间接从now到起点，得先去k加油站，而后再判断
float consumed_gas = (station[temp].dis-station[now].dis)/Davg;//从now到temp所须要加的油
if(CRemain>=consumed_gas){//油箱残余油量能够达到下一加油站，就不在now加油了
CRemain -= consumed_gas;
} else{//不够就加恰好到temp的油
cheapest += station[now].price*(consumed_gas-CRemain);
CRemain = 0;//达到temp加油站的时候恰好为0
}
now = temp;//更新下一个达到的加油站
maxDis = station[temp].dis;//更新间隔，跑到加油站temp
continue;//间接进入下一次判断了，无需再找到比now高的最低油价,因为没有比now低油价的加油站间接就开到起点了
}else{//如果没有比now更低油价的加油站，间接去起点
cheapest += station[now].price*(D-station[now].dis)/Davg;//累计跑到起点的钱
break;
}
}
int i;//保留从now加满油后，以后汽车第一个跑不到的加油站i
for(i=now+1;i<N;++i){//找到以后汽车第一个跑不到的加油站i,i-1就是所能跑到的最初一个加油站
if(station[i].dis>gap){
break;
}
}
//now+1到i-1的所有加油站就是以后汽车所能跑到的所有加油站，找到价格最近的且油价小于now的那个加油站k
int k;
for(k=now+1;k<i;++k){
if(station[k].price<station[now].price){
break;
}
}
if(k==i){//阐明没有比now更低油价的加油站，则找油价最低的
k=now+1;//对k从新赋值
for(int j=now+2;j<i;++j){
if(station[j].price<station[k].price){
k = j;
}
}
}
//在有比now加油站更低油价的时候,k保留的就是比now更低油价的加油站,如果没有k保留的就是最低油价的加油站
if(station[k].price<station[now].price){//如果下一个加油站的油更便宜，只加到恰好到k加油站的油即可
float consumed_gas = (station[k].dis-station[now].dis)/Davg;//从now到k所须要加的油
if(CRemain>=consumed_gas){//油箱残余油量能够达到下一加油站，就不在now加油了
CRemain -= consumed_gas;
} else{//不够就加恰好到k的油
cheapest += station[now].price*(consumed_gas-CRemain);
CRemain = 0;//达到k加油站的时候恰好为0
}
} else{//否则就加满
cheapest += station[now].price*CNeed;//累计加满油的钱
CRemain = Cmax-(station[k].dis-station[now].dis)/Davg;//更新达到下一个加油站的残余油量
}
now = k;//更新为下一个加油站k
maxDis = station[k].dis;//更新间隔，跑到加油站k
}
if(flag){//能跑到起点
printf("%.2f",cheapest);
}else{
printf("The maximum travel distance = %.2f",maxDis);
}
return 0;
}
发表回复