Codeforces 557B Pasha and Tea：貪心演算法最優茶水分配

Codeforces 557B 經典貪心問題：給定 2n 個茶杯（n 個男生、n 個女生），茶壺容量 w，男生喝水量為女生的 2 倍，求最大可倒水總量。

問題建模

• 女生每人分得 x 毫升，男生每人分得 2x 毫升
• 總需水量：n*x + n*2x = 3n*x
• 約束條件：

x ≤ min(女生杯容量最小值, 男生杯容量最小值 / 2)
3n*x ≤ w  (茶壺容量限制)

最優策略

1. 將 2n 個杯子容量排序
2. 前 n 個分給女生（容量較小），後 n 個分給男生（容量較大）
3. 女生限制：x ≤ a[0]（最小杯）
4. 男生限制：2x ≤ a[n] → x ≤ a[n] / 2
5. 取 x = min(a[0], a[n]/2, w/(3n))
6. 答案：3n*x

C++ 參考實作

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, w;
    cin >> n >> w;
    vector a(2 * n);
    for (int i = 0; i < 2 * n; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    
    double x = min({(double)a[0], (double)a[n] / 2.0, (double)w / (3 * n)});
    printf("%.8f\n", 3 * n * x);
    return 0;
}

範例驗證

複雜度分析

• 時間：O(n log n) — 主要為排序
• 空間：O(n) — 存儲杯子容量

關鍵洞察

將較小的杯子分給需水量較少的女生，較大的杯子分給男生，這樣能最大化 x 的上限。若反向分配，男生的 2x 會受限於較小杯子，導致整體總量下降。