POJ 2519 Dropping Tests：二分答案 + 貪心判定

POJ 2519 - 刪除 k 個測試後最大化平均分：二分法

n 門測試，第 i 門得分 a_i，滿分 b_i。刪除 k 門後，最大化累積平均 Σa / Σb。n ≤ 1000。

二分答案模型

設目標平均分為 x。判定是否存在方案使 Σa / Σb ≥ x ⇔ Σ(a_i - x·b_i) ≥ 0。定義 c_i = a_i - x·b_i，選擇 n-k 個最大的 c_i 求和，若 ≥ 0 則 x 可行。

算法流程

1. 二分 x ∈ [0, 100]（平均分百分制）
2. 每次計算所有 c_i，降序排序，取前 n-k 個求和
3. 和 ≥ 0 ⇒ l = mid，否則 r = mid
4. 迭代 ~50 次或固定次數（如 30 次）足夠精度

代碼實現

struct Node { double a, b, c; } s[1005];
bool cmp(Node x, Node y) { return x.c > y.c; }
int main() {
    int n, k;
    while (cin >> n >> k, n||k) {
        for (int i=0; i> s[i].a;
        for (int i=0; i> s[i].b;
        double l=0, r=100, mid;
        for (int iter=0; iter<30; ++iter) {
            mid = (l+r)/2;
            for (int i=0; i 0) l = mid; else r = mid;
        }
        printf("%.0lf\n", mid); // 四捨五入輸出整數
    }
}

關鍵細節

• c_i = 100*a_i - x*b_i 避免 x 為小數導致精度損失，最終輸出 mid 四捨五入
• 二分 30 次精度 ~1e-9，足夠百分制四捨五入
• 排序取最大 n-k 個，貪心最優

複雜度

O(n log n log precision)，n=1000 極快。