y总代码注释版 用的pair

题目描述

有了高速公路以后，从杭州开车到其他城市变得非常容易。

但是由于汽车的油箱容量有限，我们只能不时的寻找加油站去加油。

不同的加油站的油价可能不同。

你需要计算，到达目的地所花费的最少油钱是多少。

输入格式

第一行包含四个正整数，Cmax，油箱的最大容量，D，杭州到目的地城市的距离，Davg，每单位汽油可供汽车行驶距离，

N，加油站总数。

接下来 N 行，每行包含一对非负数描述一个加油站的相关信息，Pi，每单位汽油价格，Di，该加油站与杭州的距离。

输出格式

输出到达目的地的最小花费，保留两位小数。

假设最开始油箱是空的，如果无法到达目的地，则输出 The maximum travel distance = X，其中 X

是可以行驶的最大距离，保留两位小数。

样例

输入样例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

输出样例1：

749.17

输入样例2：

50 1300 12 2
7.10 0
7.00 600

输出样例2：

The maximum travel distance = 1200.00

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using T = pair<double, double>;   // {距离, 价格}

const int N = 510;

T w[N];
int c_max, d, d_avg, n;

int main()
{
    cin >> c_max >> d >> d_avg >> n;
    for(int i = 0; i < n; i ++ ) cin >> w[i].second >> w[i].first;
    w[n] = {d * 1.0, 0}; 
    sort(w, w + n + 1);

    if(w[0].first) // 起点没有加油站
    {
        printf("The maximum travel distance = 0.00");
        return 0;
    }

    double res = 0, pet = 0;  // pet为当前油箱中的油 初始时还未决策 故油量为0

    for(int i = 0; i < n;)
    {
        int k = -1;
        // 枚举当前油量能够走到的所有加油站 初始在0号点最远可达c_max * d_avg(油箱满)
        for(int j = i + 1; j <= n && w[j].first - w[i].first <= c_max * d_avg; j ++ )
        {
            if(w[j].second < w[i].second) // 找到第一个比起点价格小的
            {
                k = j;
                break;
            }
            // 或者找一个不比起点小但比这一段最小的
            else if(k == -1 || w[j].second < w[k].second) k = j;
        }
        if(k == -1) // 这一段之间没有加油站了
        {
            printf("The maximum travel distance = %.2lf", w[i].first + 1.0 * c_max * d_avg);
            return 0;
        }
        if(w[k].second <= w[i].second) // 存在比当前加油站更便宜的加油站 只补充合适的油
        {
            double pet_cost = (w[k].first - w[i].first) / d_avg; // 走到那个站的总耗油量
            pet_cost -= pet;     // 总耗油量减去当前油箱中的油量为需要补充的油量
            double cost = pet_cost * w[i].second; // 需要补充的油量的花费
            res += cost;
            i = k;  // 此时剩余的油量只能够正好走到下一站
            pet = 0;   // 走到下一站后油量刚好耗尽
        } 
        else    /* 可达范围内存在加油站 但价格都比当前加油站的价格更高
        此时最优选择是在当前车站把油箱填满 到了范围内最低价格的加油站再做下一步选择*/
        {
            res += (c_max - pet) * w[i].second; // 花费为: 走到[花费最优的加油站]的距离 * 油价
            pet = c_max - (w[k].first - w[i].first) / d_avg;// 走到那里时油量为:满油减去耗费的油  
            i = k;
        }
    }
    printf("%.2lf", res);
    return 0;
}