GESP 题解库 / 5 级题解 / [GESP202609 五级] 饮品调制 · 第 23 / 23 题
GESP202609 五级 · P17456 · 中等

饮品调制

各原料体积与甜度已知,求能调出甜度恰好为 t 的饮品最大体积(保留三位小数)。

📊
n ≤ ?
原料种类
🔢
double
结果类型
⚡
O(n log n)
时间复杂度
🎯
加权平均 = 目标 → 贪心削减
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有 n 种原料,第 i 种存量 vᵢ 升、每升含糖 sᵢ 克。可以自由选取用量 kᵢ ∈ [0, vᵢ](可为小数)。

最终甜度 = Σkᵢsᵢ / Σkᵢ。要求甜度恰好为 t,求能调出的最大体积,保留三位小数;若无法调制则输出 0。

💡
人话翻译:要凑出"加权平均恰好等于 t",且总量最大。关键转化:设初始用尽全部原料,此时的加权平均可能偏离 t。我们需要倒掉一些原料让平均回到 t。倒掉哪一些最"划算"?倒掉甜度偏离 t 最远的那些(每升能改变平均最多)——这样倒掉的体积最少,剩下的体积最多。

🔍 关键词提取

加权平均约束转化贪心削减浮点输出

已知条件

项目说明
输入第一行 n、t;随后 n 行 vᵢ、sᵢ
输出最大体积,保留三位小数
用量范围0 ≤ kᵢ ≤ vᵢ(连续取值)
无解时输出 0
精度保留三位小数

需要解决的问题

02
思维导图
整理解题思路的全貌
⚖️ 先全用,再最小量倒掉
🧠 建模
kᵢ ∈ [0, vᵢ] 连续
甜度 = t ⟺ Σkᵢ(sᵢ−t) = 0
设 kᵢ = vᵢ − dᵢ(dᵢ ≥ 0)
Σdᵢ(sᵢ−t) = D
📐 求偏离量
D = Σvᵢ(sᵢ−t)
若 D == 0 → 全部可用
若 D > 0 → 需减少正偏离
若 D < 0 → 需减少负偏离
🎯 贪心削减
按 |sᵢ−t| 从大到小排序
优先从"偏离方向正确"的原料倒
每升改变偏离 |sᵢ−t|
倒够了就停
⚠️ 易错点
方向判断错(该倒哪一侧)
用 int 导致精度丢失
忘了保留三位小数
全倒光时体积为 0
03
样例手算推导
样例的完整推导

🧮 样例:n = 4,t = 2

原料:(6,1)、(5,2)、(8,5)、(1,0)。每行的格式是 (体积 vᵢ, 甜度 sᵢ)。

1
第 1 步:全部用尽,看偏离

总偏离 D = Σvᵢ(sᵢ − t)

= 6 × (1 − 2) + 5 × (2 − 2) + 8 × (5 − 2) + 1 × (0 − 2)

= −6 + 0 + 24 − 2 = 16

D > 0 说明"正偏离太多",平均甜度高于 t

D = 16 > 0

2
第 2 步:判断该倒哪一侧

D > 0 意味着平均偏高,需要降低平均

所以要倒掉"甜度高于 t"的原料(sᵢ > t)

本例中 s = 5 > t = 2 的原料(体积 8)

倒掉 d 升,偏离减少 d × (5 − 2) = 3d

从 s=5 的原料倒

3
第 3 步:算出要倒多少

需要 3d = 16 → d = 16/3 ≈ 5.333

而该原料只有 8 升 ≥ 5.333 ✓ 可行

剩余体积 = (6 + 5 + 8 + 1) − 16/3

= 20 − 5.3333 = 14.6667

✅ 输出 14.667

📊 计算汇总

原料vᵢsᵢsᵢ − tvᵢ(sᵢ − t)
161−1−6
25200
385+3+24
410−2−2
合计20——+16

20 − 16/3 = 14.667 ✓

🔑
注意 s = 2 的那种原料(第 2 行):它的甜度恰好等于 t,所以加多少都不影响平均——可以全部用上,是"纯赚"的体积。这也是为什么答案能比较大。
另外注意:vᵢ(sᵢ − t) 的符号由 sᵢ − t 决定,甜度高于 t 的贡献正偏离,低于 t 的贡献负偏离。

🧮 无解的情形

什么时候答案是 0?

1
只有一种原料且甜度不等于 t

例如 n = 1,t = 5,原料 (1, 3)

D = 1 × (3 − 5) = −2 < 0

需要减少负偏离 → 倒掉 s < t 的原料

唯一原料就是 s = 3 < 5

需要 −2d = −2 → d = 1

即必须把仅有的 1 升全部倒掉 → 体积 0

❌ 输出 0

2
另一种情况

若所有原料的甜度都 ≥ t(且至少一个 > t),

D > 0,需要倒掉 s > t 的原料

而 s = t 的原料不受影响(偏离为 0)

只要有足够的 s > t 原料可倒,就能调制成功

通常可行

⚠️
精确判断"无解"的方法:如果所需倒掉的量超出了对应方向原料的总存量,那就无解。不过由 D 的定义可以证明:D ≤ Σ_{sᵢ>t} vᵢ(sᵢ − t)(D > 0 时),所以理论上总能倒够——唯一的问题是要不要把"全部原料"都倒掉,导致体积为 0。实现时只需判断最终体积是否 > 0 即可。
04
解法对比
贪心削减 vs 枚举两两混合

⚔️ 解法对比

🟢 全局贪心削减(推荐) 推荐

算总偏离 D,按 |sᵢ−t| 排序后从需要的方向贪心倒

  • 时间 O(n log n)
  • 一次排序 + 一次扫描
  • 能处理多种原料混合
  • 代码 30 行
💡
核心公式:D = Σvᵢ(sᵢ−t);若 D > 0 就从"甜度最大"开始倒,若 D < 0 就从"甜度最小"开始倒,每升改变偏离 |sᵢ − t|,倒到偏离清零为止。

🟠 枚举"用哪两种原料混合"

假设只用两种原料(一高一低)混合出甜度 t

  • 看起来可行(最优解最多用 2 种部分原料)
  • 但容易漏掉"多用几种全量原料"的情况
  • 实现更复杂
  • 不如全局贪心稳妥
⚠️
为什么容易出错:虽然线性规划理论保证"最多 2 种原料是部分使用",但"全部使用的原料"可能有很多种,枚举两两组合时很容易漏掉这些。全局贪心一次性处理所有原料,更不容易出错。

📈 性能对比

方案代码量易错程度
全局贪心约 30 行低
枚举两两约 45 行高
05
算法流程图
算偏离 → 按需削减
开始读入 n、t 和每种的 vᵢ、sᵢ;totalV = ΣvᵢD = Σ vᵢ × (sᵢ − t)D 是否等于 0?是 ✓全部可用,答案 = totalV否 ✗需要削减needed = |D|;按 |sᵢ − t| 降序排列"方向正确"的原料依次从这些原料削减:每升改变 |sᵢ − t|削减总量 = needed / |sᵢ − t|(受限不超过 vᵢ),直到 needed 为 0答案 = totalV − 削减总量,保留三位小数结束继续削减下一批
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🥤 最大可调体积计算器

第一行输入 n 和 t,随后 n 行输入每种的体积与甜度。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int main() {
    int n;
    double t;
    scanf("%d %lf", &n, &t);

    vector<double> v(n), s(n);
    double totalV = 0, D = 0;
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &v[i], &s[i]);
        totalV += v[i];
        D += v[i] * (s[i] - t);        // 总偏离
    }

    double ans = totalV;

    if (fabs(D) > 1e-9) {
        // 需要削减偏离 |D|;只从"偏离方向正确"的原料削减
        // D > 0:平均偏高,削 s > t 的原料
        // D < 0:平均偏低,削 s < t 的原料
        vector<int> idx(n);
        for (int i = 0; i < n; i++) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return fabs(s[a] - t) > fabs(s[b] - t);   // 每升改变量大者优先
        });

        double need = fabs(D), removed = 0;
        for (int k = 0; k < n && need > 1e-9; k++) {
            int i = idx[k];
            if (D > 0 && s[i] <= t) continue;          // 方向不对,跳过
            if (D < 0 && s[i] >= t) continue;
            double g = fabs(s[i] - t);
            if (g < 1e-12) continue;
            double take = min(v[i], need / g);         // 最多倒掉 v[i] 升
            removed += take;
            need -= take * g;
        }
        ans = totalV - removed;
    }

    if (ans < 1e-9) ans = 0;                            // 体积为 0 视为无法调制
    printf("%.3f\n", ans);
    return 0;
}
🔑
为什么"按 |sᵢ − t| 从大到小"削最好?因为我们的目标是让削掉的体积最少。倒掉 1 升甜度为 s 的原料,会让总偏离改变 |s − t|。所以要改变给定的偏离量,选择 |s − t| 最大的那种最"高效"——用最少的体积达成目标。这是典型的贪心论证。

📖 关键几行怎么看

代码作用为什么这样写
D += v[i] * (s[i] - t)总偏离甜度 = t 等价于总偏离为 0
fabs(s[a] - t) > fabs(s[b] - t)排序每升改变量大的优先削减
if (D > 0 && s[i] <= t) continue;方向过滤只削"偏离方向正确"的原料
double take = min(v[i], need / g);削减量取"需要的量"与"存量的量"的较小者
printf("%.3f", ans)输出保留三位小数
⚠️
三个坑:① 削减方向搞反(D > 0 时应削 s > t 的原料);② 用 int 计算(体积可以是小数,必须用 double);③ 忘记保留三位小数(用 %.3f)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4 2
6 1 / 5 2 / 8 5 / 1 0
14.667题面样例
1 5
1 5
1.000唯一原料甜度恰好等于 t,全部可用
1 5
1 3
0.000无法调制:只有一种原料且甜度 ≠ t
2 2
1 1 / 1 3
2.000一低一高,各用 1 升混合,平均恰好为 2
2 5
3 5 / 4 5
7.000全部甜度都等于 t,全部可用
✅
自查清单:① 削减方向对吗?② 用 double 了吗?③ 输出三位小数了吗?

🚨 易错点清单

⚠️
削减方向反了:D > 0(平均偏高)时应削减甜度大于 t 的原料。
⚠️
用整数运算:体积可以是小数,必须用 double 并注意精度(比较用 fabs(x) < 1e-9)。
⚠️
输出格式:必须保留三位小数(%.3f)。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n)
n 规模
不大
运算量
排序为主

时间怎么算的?

空间都用在哪?

需要存下 n 种的体积与甜度。

✅ 排序是主要开销,任何规模都轻松完成。难点在于把"加权平均等于 t"转化为"总偏离为 0"这个约束。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 本题的数学核心
// 甜度 = Σkᵢsᵢ / Σkᵢ = t
//   <=>  Σkᵢsᵢ = t·Σkᵢ
//   <=>  Σkᵢ(sᵢ − t) = 0        (总偏离为 0)

// 令 kᵢ = vᵢ − dᵢ(dᵢ 为倒掉的量,dᵢ ∈ [0, vᵢ])
//   Σ(vᵢ − dᵢ)(sᵢ − t) = 0
//   Σvᵢ(sᵢ − t) = Σdᵢ(sᵢ − t)
//   即 D = Σdᵢ(sᵢ − t),要最小化 Σdᵢ
//   -> 用 |sᵢ − t| 最大的原料去"抵消" D

// 浮点比较的惯用写法
if (fabs(x) < 1e-9) { /* 视为 0 */ }

// 输出固定小数位
printf("%.3f\n", ans);

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
约束转化平均值 = t ⟺ 总偏离 = 0混合问题、加权平均类题目
贪心削减用"最有效"的资源凑出目标量所有"最小代价达成目标"的问题
浮点精度fabs(x) < 1e-9 判零所有涉及小数的比较
🌟
思考题:如果原料的用量只能取整数升(不能取小数),这题会变成什么?(提示:那就不再是简单的贪心,而更像背包问题——需要 DP 或更复杂的搜索,因为它变成了整数规划。"连续取值"这个条件是本题能用贪心的关键前提。)