HDOJ 4968 Improving the GPA：平均分轉換4.0制GPA的極值枚舉法

問題重述

給定 N 門課的平均分 avg（保證總分可被 N 整除），每門課分數為 60~100 整數。根據固定的分數-綠點對應表，求所有可能分數分佈下，4.0 制 GPA 的最小值與最大值。

對應表：

解題思路：五重循環枚舉 + 可行性剪枝

由於 N ≤ 10，總分 sum = avg × N ≤ 1000，可直接枚舉五個區間的課程數 l1..l5（分別對應 4.0, 3.5, 3.0, 2.5, 2.0），滿足 Σli = N。對每種分配，計算其最小可能總分 minScore 和最大可能總分 maxScore：

• minScore = 85×l1 + 80×l2 + 75×l3 + 70×l4 + 60×l5
• maxScore = 100×l1 + 84×l2 + 79×l3 + 74×l4 + 69×l5

若 sum ∈ [minScore, maxScore]，則該分配可行，累積 GPA 總和 4.0×l1 + 3.5×l2 + ... 更新極值。

C++ 實現代碼

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

int level[5][2] = {{100,85}, {84,80}, {79,75}, {74,70}, {69,60}};
double gpa[5] = {4.0, 3.5, 3.0, 2.5, 2.0};

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int avg, n; scanf("%d%d", &avg, &n);
        int sum = avg * n;
        double mn = 1e9, mx = -1e9;
        
        for (int l1=0; l1<=n; l1++)
        for (int l2=0; l2<=n-l1; l2++)
        for (int l3=0; l3<=n-l1-l2; l3++)
        for (int l4=0; l4<=n-l1-l2-l3; l4++) {
            int l5 = n - l1 - l2 - l3 - l4;
            int minS = level[0][1]*l1 + level[1][1]*l2 + level[2][1]*l3 + level[3][1]*l4 + level[4][1]*l5;
            int maxS = level[0][0]*l1 + level[1][0]*l2 + level[2][0]*l3 + level[3][0]*l4 + level[4][0]*l5;
            if (sum >= minS && sum <= maxS) {
                double val = (gpa[0]*l1 + gpa[1]*l2 + gpa[2]*l3 + gpa[3]*l4 + gpa[4]*l5) / n;
                mn = min(mn, val);
                mx = max(mx, val);
            }
        }
        printf("%.4lf %.4lf\n", mn, mx);
    }
    return 0;
}

關鍵點總結

• 枚舉空間小：N≤10 使得五重循環極快（約 C(14,4)=1001 次）
• 區間可行性判定：只需比較總分是否落在該分配的理論分數區間內
• 精度控制：輸出保留 4 位小數，用 double 足夠

此題展示了「暴力枚舉 + 數學邊界判定」在小規模約束下的威力，避免了複雜 DP 的實現負擔。