NYOJ Yougth的最大化：二分答案 + 貪心選擇解分數規劃

題目大意

n (≤ 10000) 個物品，重量 W[i]、價值 V[i]。選**恰好 k** 個物品，使**單位重量價值** (ΣV / ΣW) 最大。輸出最大值（保留兩位小數）。多測試案例。

核心模型：分數規劃 + 二分答案

設最大值為 ans。對任意候選值 x，判斷是否存在 k 個物品使 ΣV / ΣW ≥ x。
等價變形：Σ(V[i] - x·W[i]) ≥ 0。
定義 a[i] = V[i] - x·W[i]。選最大的 k 個 a[i] 求和，若和 ≥ 0 則 x 可行。
單調性：x 越大，可行性越難。故可二分 x。

算法流程

1. 二分上界 `right = max(V[i]/W[i])`，下界 `left = 0`。
2. 精度 `eps = 1e-3`（保證輸出兩位小數正確）。
3. 檢查函數 `check(x)`：
   計算所有 `a[i]`，降序排序，取前 k 個求和，返回 `sum >= 0`。
   時間 O(n log n)。
4. 二分循環：`mid = (l+r)/2`，`check(mid)` 為真則 `l=mid` 否則 `r=mid`。
5. 輸出 `l` 保留兩位小數。

代碼

#include 
#include 
#include 
using namespace std;
const double EPS = 1e-3;
const int MAXN = 10005;
double V[MAXN], W[MAXN];
int n, k;

bool check(double x) {
    static double a[MAXN];
    for (int i = 0; i < n; ++i) a[i] = V[i] - x * W[i];
    sort(a, a+n, greater());
    double sum = 0;
    for (int i = 0; i < k; ++i) sum += a[i];
    return sum >= 0;
}

int main() {
    while (cin >> n >> k) {
        double right = 0;
        for (int i = 0; i < n; ++i) {
            cin >> W[i] >> V[i];
            right = max(right, V[i] / W[i]);
        }
        double l = 0, r = right;
        while (r - l > EPS) {
            double mid = (l + r) / 2;
            if (check(mid)) l = mid;
            else r = mid;
        }
        printf("%.2lf\n", l);
    }
    return 0;
}

複雜度

• 每次 `check`：O(n log n)。
• 二分次數：log₂(10⁶ / 10⁻³) ≈ 30 次。
• 總時間：O(30 · n log n) ≈ 30 × 10⁴ × 14 ≈ 4.2×10⁶，極快。

關鍵點

• **分數規劃標準轉化**：`ΣV/ΣW ≥ x ⇔ Σ(V - xW) ≥ 0`。
• **貪心選擇**：為使 Σ(V - xW) 最大，只需選最大的 k 個 `V - xW`。
• **精度控制**：`eps = 1e-3` 足夠保證 `%.2lf` 正確（實際可用 1e-4 更穩）。
• **上界**：單個物品最大單位價值是整體最大值的上界。

總結

NYOJ「Yougth的最大化」是分數規劃（0-1 分數背包固定選 k 項）的教科書級例題。**二分答案 + 貪心檢查** 是解決此類「最大化比值」問題的通用模板，代碼簡潔、通用性強。