摘要
Title: A1033 To Fill or Not to Fill
Tag: 贪心
Memory Limit: 64 MB
Time Limit: 1000 ms

A1033 To Fill or Not to Fill

题意

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.
思路

题意：需要从起点走到终点，期间需要加油，路上有加油站，每个加油站有各自的位置和油钱，问最少的花费到终点，如果到不了终点，则输出最远距离

思路
- 每次顺次向后搜索加油站，范围是加满油能达到的最远距离之前的所有加油站
- 找到最近的比当前加油站便宜的加油站，在当前只要加到能到那个加油站的油即可
- 如果到达最远的距离仍旧没有比当前加油站更便宜的加油站，就在当前把油加满，并且下一次停在能到达范围内的加油站中最便宜的加油站
- 以此类推向后迭代，重复1，2，3

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 510, INF = 0x3f3f3f3f;

int c_max, d, d_avg, n;
struct sa
{
    double p, d;

    bool operator<(const sa &t) const
    {
        return d < t.d;
    }
};

signed main()
{
    IOS;
    cin >> c_max >> d >> d_avg >> n;
    vector<sa> s;
    for (int i = 0; i < n; i++)
    {
        double p, d;
        cin >> p >> d;
        s.push_back({p, d});
    }
    s.push_back({0, (double)d}); // 加入终点，终点是距离为d，花费为0的加油站

    sort(s.begin(), s.end());

    if (s[0].d)
    {
        printf("The maximum travel distance = 0.00");
        return 0;
    }

    double res = 0, oil = 0; // res为花费，oil为当前油含量
    for (int i = 0; i < n;)
    {
        int k = -1; // 找最近的加油站

        for (int j = i + 1; j <= n && s[j].d - s[i].d <= c_max * d_avg; ++j)
        {
            if (s[j].p < s[i].p)
            { // 找最近的且比当下便宜的加油站
                k = j;
                break;
            }
            else if (k == -1 || s[j].p < s[k].p)
                k = j; // 找相对小的
        }
        if (k == -1)
        {
            printf("The maximum travel distance = %.2lf\n",
                  s[i].d + (double)c_max * d_avg); // 如果走不到终点，则最远距离为目前的距离加上剩下油跑的距离
            return 0;
        }

        if (s[k].p <= s[i].p) // 第一种情况，直接去最近的便宜处加油
        {
            res += ((s[k].d - s[i].d) / d_avg - oil) * s[i].p;
            i = k;
            oil = 0;
        }
        else
        {
            res += (c_max - oil) * s[i].p;
            oil = c_max - (s[k].d - s[i].d) / d_avg;
            i = k;
        }
    }
    printf("%.2lf\n", res);

    return 0;
}

A1033 To Fill or Not to Fill

题意

思路

代码