PAT A1033测试点0无法通过

我就很纳闷，连自测用例都通过不了，这个数值差异到底是怎么来的？

运行结果是757.92，但预期结果是749.17 运行结果是757.92，但预期结果是749.17

 

我的思路按照《算法笔记》提供，如下：

/*
 * Notes:
 *
 * 这属于比较复杂的一道贪心算法题，难点在于分析出算法步骤
 * 但总结下来题型典型，值得记忆练习
 * 1、如果最近的加油站距离非0，则无法驶出起点RETURN 0
 * 2、将终点视为费用为0的加油站，并入加油站队列中
 * 3、遍历当前可触及范围内所有加油站：
 *      （1）优先选中最近的价格低于当前价格的加油站
 *      （2）如无则选中范围内价格最低的加油站
 *      （3）如无则说明可触及范围内没有加油站，则无法继续驾驶 RETURN DISTANCE
 * 4、正常结束后返回费用
 *
 * 第一个测试点到底怎么回事？
 * */

我的代码如下：

// A1033 To Fill or Not to Fill (25 分)
// Start : 2021年2月4日20:06:30
// Finish :

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAX_STATION_NUM = 510;

struct Station {
    double unitPrice;
    double distance;
} stations[MAX_STATION_NUM]{};

bool cmp(Station a, Station b) {
    return a.distance < b.distance;
}

int main() {
    setbuf(stdout, NULL);

    double capacity, totalDistance, distancePerGas;
    int stationNum;
    scanf("%lf %lf %lf %d", &capacity, &totalDistance, &distancePerGas, &stationNum);
    double range = capacity * distancePerGas;
    stationNum++;

    for (int i = 0; i < stationNum - 1; ++i) {
        scanf("%lf %lf", &stations[i].unitPrice, &stations[i].distance);
    }
    stations[stationNum - 1].unitPrice = 0;
    stations[stationNum - 1].distance = totalDistance;

    sort(stations, stations + stationNum, cmp);

    double distance = 0.0;
    if (stations[0].distance > 0) {
        printf("The maximum travel distance = %.2f", distance);
        return 0;
    }

    double fare = 0.0;
    int now = 0, next;
    double nowPrice = stations[0].unitPrice;
    double cheapestPrice;
    double fuelDemand;
    while (now != stationNum - 1) {
        cheapestPrice = 999999;
        next = -1;
        for (int i = now + 1; i < stationNum && stations[i].distance - stations[now].distance <= range; ++i) {
            if (stations[i].unitPrice < nowPrice) {
                next = i;
                break;
            } else {
                if (stations[i].unitPrice <= cheapestPrice) {
                    cheapestPrice = stations[i].unitPrice;
                    next = i;
                }
            }
        }
        if (next == -1) {
            distance += range;
            printf("The maximum travel distance = %.2f", distance);
            return 0;
        } else {
            distance += stations[next].distance - stations[now].distance;
            fare += nowPrice * (stations[next].distance - stations[now].distance) / distancePerGas;
            nowPrice = stations[next].unitPrice;
            now = next;
        }
    }
    printf("%.2f", fare);
    return 0;
}

 

不知道你这个问题是否已经解决, 如果还没有解决的话:

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^