PAT1033 - To Fill or Not to Fill

此题考察的是贪心算法。

解题思路： 在起点加油，加多少不确定。记录当前油价，从下一站开始查找，满足条件 下一站的dis <= (当前dis + 加满油最多的距离)，如果遇到此站的油价小于当前油价，则从上一站加油只需要加到能够跑到此站为止即可，若满足条件的站点的油价都大于上一次当前站的油价，那么当前油加满，记录跑到此站的剩余油量，供下次计算油量的时候减去即可。
总之，贪心算法就是尽可能加最便宜的油，跑最远的路。

坑位：

1. 起点若没有加油站，则输出printf("The maximum travel distance = 0.00\n");
2. 此代码PAT全部AC，但是牛客只通过81.82%，有一个测试案例无法通过
   用例:
   21 474 15 10
   1239036029 0
   37 27
   93 194
   28 27
   11 432
   29 182
   4 469
   63 401
   38 122
   40 136

对应输出应该为:

2230265642.67

你的输出为:

2230265525.33

// runtime: 4ms
// space: 424K
// https://pintia.cn/problem-sets/994805342720868352/problems/994805458722734080
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
struct OilStation {
    int dis;
    double price;

    OilStation(int d, double p): dis(d), price(p) {}
};

bool cmp(OilStation a, OilStation b) {
    return a.dis < b.dis;
}

vector<OilStation> v;

int main() {
    int C, D, avg, N;
    scanf("%d %d %d %d", &C, &D, &avg, &N);
    int MAX = C * avg;

    for (int i = 0; i < N; ++i) {
        double p;
        int d;
        scanf("%lf %d", &p, &d);

        v.push_back(OilStation(d, p));
    }

    sort(v.begin(), v.end(), cmp);

    int currentS = 0; // 当前station
    int nextS; // 下一个station
    double currentP = v[currentS].price; // 当前price
    double nextP; // 下一站price
    int dis = 0; // 当前距离
    double sum = 0.0;
    int leftDis = 0; // 上次加满后到nextP处还能走的距离。
    int type; // 加油类型

    // 有一个检测点起点就不是0，很坑。
    if (v[0].dis != 0) {
        printf("The maximum travel distance = 0.00\n");
        return 0;
    }

    while (dis <= D) {
        type = -1; // 已经到了最后一站
        nextP = 10000.0; // 假设成一个很大的值。
        for (int i = currentS + 1; i < N; ++i) {
            if (v[i].dis <= v[currentS].dis + MAX) {
                if (nextP > v[i].price) {
                    nextP = v[i].price;
                    nextS = i;
                }
            } else {
                break;
            }

            if (nextP <= currentP) {
                type = 1; // 遇到了更便宜的油，上一次加油加到此处
                break;
            } else {
                type = 2; // 上次加的油就是最便宜的，上一次加满
            }
        }

        if (type == 1) {
            // 遇到了更便宜的油，而且没到终点
            sum += (v[nextS].dis - dis - leftDis) * currentP;
        } else if (type == 2) {
            if (v[currentS].dis + MAX >= D) {
                // 能够到达
                sum += (D - v[currentS].dis) * v[currentS].price;
                printf("%.2lf\n", sum / 1.0 / avg);
                break;
            } else {
                // 还没到达终点
                sum += v[currentS].price * (MAX - leftDis);
                leftDis = dis + MAX - v[nextS].dis;
            }
        } else {
            // type == -1
            if (v[currentS].dis + MAX >= D) {
                // 能够到达
                sum += (D - v[currentS].dis) * v[currentS].price;
                printf("%.2lf\n", sum / 1.0 / avg);
                break;
            } else {
                // 不能到达终点
                printf("The maximum travel distance = %.2lf\n", double(v[currentS].dis + MAX));
                break;
            }
        }

        dis = v[nextS].dis; // 更新距离
        currentP = nextP;
        currentS = nextS;
    }
    return 0;
}