經典算法題「加油站最小花費」C語言完整解法：貪心策略與遞歸實現

編輯：關於C語言

問題描述 (九度 OJ 第 25 題 / POJ 2431 / 洛谷 P1090 類似)

汽車從起點駛向終點，距離 L。油箱容量 Cmax，滿油可行駛 Cmax * Davg 距離。沿途有 N 個加油站，每站有位置 D[i] 和單價 P[i]。起點視為第 0 站 (位置 0，價格 0)，終點視為第 N+1 站 (位置 L，價格 INF)。求**最小加油花費**，若無法到達輸出最大可達距離。

核心貪心策略

按位置排序所有加油站 (含起點、終點)。
可達性檢查：相鄰兩站距離 > Cmax * Davg → 無法到達，輸出最大距離。
決策規則 (在當前站 i，油量 oil)：
1. 前方可達範圍內有更便宜的站 j：僅加夠到達 j 的油，駛向 j，到達時油量為 0。
2. 前方可達範圍內無更便宜站：
  - 若終點在可達範圍內：加夠直達終點的油，結束。
  - 否則：在可達範圍內找最便宜站 k，加滿油駛向 k，到達 k 時剩餘油量扣除路程消耗。

關鍵數據結構


#define MAXN 600
typedef struct {
    double price; // 單價
    double length; // 距起點距離
} Station;

Station sta[MAXN + 2]; // 0: 起點, 1..N: 加油站, N+1: 終點
double Cmax, L, Davg;  // 油箱容量, 總距離, 單位距離耗油
double maxDist;        // 滿油可行距離 = Cmax * Davg
int N;                 // 加油站數量

核心函數解析

1. `find(i)`：尋找可達範圍內第一個比當前站便宜的站


int find(int i) {
    int j, fprice = INT_MAX;
    double price = INT_MAX;
    for (j = i + 1; j <= N + 1 && sta[i].length + maxDist >= sta[j].length; j++) {
        if (sta[j].price < price && sta[j].price < sta[i].price) {
            price = sta[j].price;
            fprice = j;
        }
    }
    return (fprice <= N && sta[fprice].price < sta[i].price) ? fprice : -1;
}

2. `findmin(i)`：尋找可達範圍內最便宜的站 (不要求比當前便宜)


int findmin(int i) {
    int j, fprice = INT_MAX;
    double price = INT_MAX;
    for (j = i + 1; j <= N + 1 && sta[i].length + maxDist >= sta[j].length; j++) {
        if (sta[j].price < price) {
            price = sta[j].price;
            fprice = j;
        }
    }
    return (fprice <= N + 1) ? fprice : -1;
}

3. `pri(i, oil)`：遞歸決策主函數


double totalCost = 0;

void pri(int i, double oil) {
    int j = find(i); // 找更便宜的站
    if (j != -1) {
        // 策略 1：前方有更便宜站，僅加夠到達最近的更便宜站 k
        int k = i + 1;
        while (k <= j && sta[k].price >= sta[i].price) k++;
        // 加油量 = (距離差/耗油) - 現有油量
        totalCost += ((sta[k].length - sta[i].length) / Davg - oil) * sta[i].price;
        pri(k, 0); // 到達 k 時油量為 0
    } else {
        // 策略 2：前方無更便宜站
        if (sta[i].length + maxDist >= sta[N + 1].length) {
            // 2.1 終點可達，直接加夠到達終點
            totalCost += ((sta[N + 1].length - sta[i].length) / Davg - oil) * sta[i].price;
        } else {
            // 2.2 終點不可達，找可達範圍內最便宜站 k，加滿油過去
            int k = findmin(i);
            totalCost += (Cmax - oil) * sta[i].price; // 加滿
            // 遞歸到 k，剩餘油量 = 滿油 - 路程消耗
            pri(k, Cmax - (sta[k].length - sta[i].length) / Davg);
        }
    }
}

主流程與邊界處理


int main() {
    while (scanf("%lf %lf %lf %d", &Cmax, &L, &Davg, &N) != EOF) {
        maxDist = Cmax * Davg;
        for (int i = 1; i <= N; i++)
            scanf("%lf %lf", &sta[i].price, &sta[i].length);
        
        qsort(sta + 1, N, sizeof(Station), cmp); // 按距離排序
        
        sta[0].length = 0; sta[0].price = 0;       // 起點
        sta[N + 1].length = L; sta[N + 1].price = INT_MAX; // 終點
        
        // 可達性預檢
        bool reachable = true;
        if (sta[1].length > 0) reachable = false; // 起點無加油站 (第一站距離>0)
        for (int i = 1; i <= N; i++)
            if (sta[i + 1].length - sta[i].length > maxDist) reachable = false;
        
        if (!reachable) {
            // 輸出最大可達距離
            double maxReach = 0;
            for (int i = 0; i <= N; i++) {
                if (sta[i + 1].length - sta[i].length > maxDist) {
                    maxReach = sta[i].length + maxDist;
                    break;
                }
            }
            printf("The maximum travel distance = %.2f\n", maxReach);
        } else {
            totalCost = 0;
            pri(0, 0); // 從起點出發，油量 0
            printf("%.2f\n", totalCost);
        }
    }
    return 0;
}