区间贪心算法,后一个区间的起点较前一区间偏移多少,区间终点也会偏移多少,所以不用考虑油箱容积的变化。另外浮点数需使用double,float不能通过测试。

#include <iostream>
#include <algorithm>
using namespace std;
struct station {
    double price;
    int distance;
};
bool compare(station a, station b) {
    return a.price <= b.price;
}
int main() {
    int cmax, d, davg, n;
    while (cin >> cmax >> d >> davg >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        station stationList[n];
        for (int i = 0; i < n; i++) {
            cin >> stationList[i].price >> stationList[i].distance;
        }
        sort(stationList, stationList + n, compare);
        bool way[d + 1];
        for (int i = 0; i < d + 1; i++) way[i] = false;
        int farest = cmax * davg;
        double price = 0;
//从油价最低的加油站开始,尽肯能多的去规划里程
        for (auto station : stationList) {
            int distance = 0;
            for (int j = station.distance + 1; j <= d &&
                    j <= station.distance + farest; j++) {
                if (way[j] == false) {
                    way[j] = true;
                    distance++;
                }  
            }
            price += distance / (davg * 1.0)* station.price;
        }
        bool finish = true;
        double allDistance = 0;
        for (int i = 1; i < d+ 1; i++) {
            if (way[i] == false) {
                finish = false;
                break;
            } else allDistance++;
        }
        if (finish == true) printf("%.2f\n", price);
        else printf("The maximum travel distance = %.2f\n", allDistance);
    }
}
// 64 位输出请用 printf("%lld")// 64 位输出请用 printf("%lld")