*PAT_甲级_1033 To Fill or Not to Fill (25分) (C++)【贪心算法】

目录

​​1，题目描述​​

​​题目大意​​

​​输入​​

​​输出​​

​​说明​​

​​2，思路​​

​​数据结构​​

​​算法​​

​​3，代码​​

1，题目描述

Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample Output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

The maximum travel distance = 1200.00

题目大意

输入

1. 第一行：Cmax（<=100）油箱最大容量，D（<=30000）杭州到目标城市的距离，Davg（<= 20）每单位汽油可行驶的路程，N（<=500）加油站的总数；
2. 接下来的N行：每单位燃料的价格Pi，当前加油站到杭州的距离Di（编号1-N）

输出

1. 最少花费（精确到两位小数）；
2. 若无法到达目的地，输出：The maximum travel distance = X（X为最远距离，精确到两位小数）；

说明

1. 出发时，油箱油量为0；

2，思路

典型的贪心算法（第一次接触到这样的题目，花了不少力气理解。。。）

参考这位大神的代码​​@ strivinging 【PAT甲级1033】​​

数据结构

• struct station{double price, dis;}：结构体存放每个站点的收费，距离；
• vector<station> sta(n + 1)：存放所有站点信息；（按照距离升序排序，新添加站点{0，d}保证跳出循环）

算法

1. 接受所有站点信息以及 {0，d}，并按照距离升序排序；
2. 若第一个站点距出发点的距离不为0，则最远可达距离为0；
3. 否则，利用while循环控制是否到达目的地：

• 选择站点：遍历当前站点now之后且满油状态下可达的所有站点，选择第一个价格低于站点now的站点k，或者其中价格最低的站点k；
• 计算到达选择站点的耗费：若找到第一个价格低于站点now的站点，则只需将油加到可以到达k即可（油量足够，则不需要加，当前油箱容量nowTank减去耗费（nowTank-need）即可；否则，须在当前站点补充，使其正好到达站点k，nowTank置0）；否则，当前站点价格最实惠，需要加满，同时，减去到达站点k的损耗（nowTank-need）；
• 更新当前站点为k（now = k）

    4.若当前站点的距离正好为目标距离d，即顺利到达目的地，输出花费totalPrice；否则输出最长到达距离sta[now].dis + Cmax * Davg;

3，代码

#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;

struct station{
    double price, dis;                  //距离可能为小数 故声明为double类型
};
bool cmp(station a, station b){
    return a.dis < b.dis;
}

int main(){
//#ifdef ONLINE_JUDGE
//#else
//    freopen("1.txt", "r", stdin);
//#endif

    double Cmax, d, Davg;               //Cmax油箱最大容量 d路程 Davg单位燃料行驶距离
    int n;                              //加油站数目
    scanf("%lf%lf%lf%d", &Cmax, &d, &Davg, &n);

    vector<station> sta(n + 1);
    sta[0] = {0.0, d};                  //当遍历完n个站点后 遇到此新加的'站点'必会跳出循环（已得出答案）
    for(int i = 1; i <= n; i++)
        scanf("%lf%lf", &sta[i].price, &sta[i].dis);
    sort(sta.begin(), sta.end(), cmp);

    if(sta[0].dis != 0){                //起始时油箱内无油 第一个若不在起点则无法前进
        printf("The maximum travel distance = 0.00");
        return 0;
    }

    int now = 0;                        //当前加油站编号
    double totalPrice = 0, nowTank = 0, MAX = Cmax * Davg;//totalPrice总油费 nowTank当前油量 MAX满油状态最大行驶距离

    //每次选出下一个将要到达的加油站
    while(sta[now].dis < d){
        int k = -1;
        double minPrice = INT_MAX;

        //在满油可达距离范围内 选择价格最低的站点
        for(int i = now + 1; i <= n && sta[i].dis - sta[now].dis <= MAX; i++){//i<=n
            if(sta[i].price < sta[now].price){//选择第一个低于当前站点的价格的站点
                k = i;
                break;
            }else if(sta[i].price < minPrice){//若在当前站点最远可达范围内 无低于当前站点价格的地方 则选择其中价格最低的
                k = i;
                minPrice = sta[i].price;
            }
        }
        if(k == -1) break;

        //计算到达站点k耗油
        double need = (sta[k].dis - sta[now].dis) / Davg;   //从当前站点到达目的站点需要耗油
        if(sta[k].price < sta[now].price){                  //此时油量只需达到站点k即可
            if(nowTank < need){                             //目前的油量不足 需要在当前站点补充
                totalPrice += (need - nowTank) * sta[now].price;
                nowTank = 0;
            }else{                                          //油量充足
                nowTank -= need;
            }
        }else{                                              //站点k的价格高于当前站点的价格 故在此站点加满
            totalPrice += (Cmax - nowTank) * sta[now].price;
            nowTank = Cmax - need;                          //这里的nowTank是到达下一站时的容量 所以需要减去need
        }
        now = k;                                            //更新站点
    }

    if(sta[now].dis == d) printf("%.2f", totalPrice);
    else printf("The maximum travel distance = %.2f", sta[now].dis + MAX);

    return 0;
}