您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

ZOJ 1409 通訊系統：貪心算法與枚舉優化詳解

編輯：關於C++

ZOJ 1409「通訊系統」是一道經典的貪心算法題目，核心在於最大化帶寬與價格的比值 B/P。由於 B 取決於所有設備中最小的帶寬，P 為所有設備總價格，因此我們需要讓分母 P 盡可能小、分子 B 盡可能大。本文將詳細解析如何結合枚舉與貪心策略高效求解。

核心思路：枚舉最小帶寬 B

題目要求最大化 B/P，其中 B 為所選設備中的最小帶寬。我們可以枚舉所有可能的帶寬值作為候選 B，對於每一個候選帶寬 band，檢查是否能為每類設備選擇一個帶寬 ≥ band 的廠家，並使總價格最小。若某類設備無滿足條件的廠家，則該 band 不可行，隨著 band 遞增，一旦不可行即可終止枚舉。

貪心選擇策略

給定候選帶寬 band 後，對每類設備獨立決策：在所有帶寬 ≥ band 的廠家中，選擇價格最低者。這符合貪心選擇性質，局部最優（單類設備最便宜）能推導出全局最優（總價格最小）。

優化細節

帶寬預處理：收集所有廠家的帶寬值，去重並升序排序，作為枚舉序列。
設備內部排序：對每類設備的廠家按帶寬降序排序。查找滿足 band 且價格最低的廠家時，可從高帶寬向低帶寬掃描，首個滿足條件者即為最優（因同帶寬下價格可能不同，需記錄最小值）。
提前剪枝：枚舉時從最小帶寬開始，若某 band 導致某類設備無可用廠家，後續更大的 band 必然也無解，直接結束。

複雜度分析

設 n 為設備類數，m 為最大廠家數，總帶寬種類數 ≤ n×m。枚舉帶寬 O(n×m)，每次檢查所有設備 O(n×m)，總複雜度 O(n²m²)。實測在題目限制下僅需 0ms，極其高效。

關鍵代碼實現（C++）

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 1 << 28;
const int MAXN = 102;
const int MAXM = 10002;

struct Device {
    int band, price;
} dev[MAXN][MAXN];

int bandList[MAXM];
int devCount[MAXN];
int n, m;

int solve(int targetBand) {
    int totalPrice = 0;
    for (int i = 1; i <= n; ++i) {
        int minPrice = INF;
        for (int j = 1; j <= devCount[i]; ++j) {
            if (dev[i][j].band >= targetBand)
                minPrice = min(minPrice, dev[i][j].price);
        }
        if (minPrice == INF) return -1; // 無可用廠家
        totalPrice += minPrice;
    }
    return totalPrice;
}

bool cmpBandDesc(const Device& a, const Device& b) {
    return a.band > b.band;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int bandTop = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &m);
            devCount[i] = m;
            for (int j = 1; j <= m; ++j) {
                scanf("%d%d", &dev[i][j].band, &dev[i][j].price);
                bandList[++bandTop] = dev[i][j].band;
            }
            sort(dev[i] + 1, dev[i] + m + 1, cmpBandDesc);
        }
        sort(bandList + 1, bandList + bandTop + 1);
        bandTop = unique(bandList + 1, bandList + bandTop + 1) - bandList - 1;

        double bestRatio = 0.0;
        for (int i = 1; i <= bandTop; ++i) {
            int price = solve(bandList[i]);
            if (price == -1) break;
            double ratio = bandList[i] * 1.0 / price;
            if (ratio > bestRatio) bestRatio = ratio;
        }
        printf("%.3lf\n", bestRatio);
    }
    return 0;
}