关于算法-数据结构:PAT甲级1033-To-Fill-or-Not-to-Fill

已知终点与起点的间隔为 D, 油箱的最大油量为 Cmax, 单位汽油可能反对后退 Davg。给定 N 个加油站的单位油价和离终点的间隔 C 所有加油站都在一条线上)，汽车初始时刻处于终点地位，油箱为空，且能够在任意加油站购买任意量的汽油(前提是不超过油箱容量)，求从终点到起点的最小破费。如果无奈达到起点，则输入可能行驶的最远距离。

此题考查的是贪婪算法的思维，这里次要阐明加油站的抉择策略，并且提供 2 中不同的实现代码。对于每一个加油站，假如以后加油站为 j，汽车能够行驶
的最大间隔为 max_dis。咱们首先在从加油站 j 能够达到的最远加油站 (距杭州的间隔小于等于加油站 j 加上 max_dis) 之间进行遍历，如果能够找到比加油站 j 油价低的加油站，那么抉择间隔 j 最近的加油站为下一站。如果没有，那么找到油价最低的加油站作为下一站。如果从加油站 j 没有能够达到的加油站，那么阐明没法后退，以后加油站的间隔加上 max_dis 就是最大行驶间隔.

应用 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

相比拟于算法实现 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.00

#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;
}

#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;
}

关于算法-数据结构:PAT甲级1033-To-Fill-or-Not-to-Fill

题目粗心：

算法思路：

算法实现 1：

算法实现 2：

留神点：

提交后果：

测试用例：

AC 代码 1：

AC 代码 2：

Just My Socks（注册教程内含优惠码）

关于算法-数据结构:PAT甲级1033-To-Fill-or-Not-to-Fill

题目粗心：

算法思路：

算法实现 1：

算法实现 2：

留神点：

提交后果：

测试用例：

AC 代码 1：

AC 代码 2：

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）