各原料体积与甜度已知,求能调出甜度恰好为 t 的饮品最大体积(保留三位小数)。
有 n 种原料,第 i 种存量 vᵢ 升、每升含糖 sᵢ 克。可以自由选取用量 kᵢ ∈ [0, vᵢ](可为小数)。
最终甜度 = Σkᵢsᵢ / Σkᵢ。要求甜度恰好为 t,求能调出的最大体积,保留三位小数;若无法调制则输出 0。
加权平均约束转化贪心削减浮点输出
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、t;随后 n 行 vᵢ、sᵢ |
| 输出 | 最大体积,保留三位小数 |
| 用量范围 | 0 ≤ kᵢ ≤ vᵢ(连续取值) |
| 无解时 | 输出 0 |
| 精度 | 保留三位小数 |
Σkᵢ(sᵢ − t) = 0,即"正偏离总量 = 负偏离总量"vᵢ − dᵢ(dᵢ 是"倒掉的量"),则目标是最小化 Σdᵢ|sᵢ − t| 最大的那种——它每升能改变偏离最多原料:(6,1)、(5,2)、(8,5)、(1,0)。每行的格式是 (体积 vᵢ, 甜度 sᵢ)。
总偏离 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
D > 0 意味着平均偏高,需要降低平均
所以要倒掉"甜度高于 t"的原料(sᵢ > t)
本例中 s = 5 > t = 2 的原料(体积 8)
倒掉 d 升,偏离减少 d × (5 − 2) = 3d
从 s=5 的原料倒
需要 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ᵢ − t | vᵢ(sᵢ − t) |
|---|---|---|---|---|
| 1 | 6 | 1 | −1 | −6 |
| 2 | 5 | 2 | 0 | 0 |
| 3 | 8 | 5 | +3 | +24 |
| 4 | 1 | 0 | −2 | −2 |
| 合计 | 20 | — | — | +16 |
20 − 16/3 = 14.667 ✓
vᵢ(sᵢ − t) 的符号由 sᵢ − t 决定,甜度高于 t 的贡献正偏离,低于 t 的贡献负偏离。什么时候答案是 0?
例如 n = 1,t = 5,原料 (1, 3)
D = 1 × (3 − 5) = −2 < 0
需要减少负偏离 → 倒掉 s < t 的原料
唯一原料就是 s = 3 < 5
需要 −2d = −2 → d = 1
即必须把仅有的 1 升全部倒掉 → 体积 0
❌ 输出 0
若所有原料的甜度都 ≥ t(且至少一个 > t),
D > 0,需要倒掉 s > t 的原料
而 s = t 的原料不受影响(偏离为 0)
只要有足够的 s > t 原料可倒,就能调制成功
通常可行
D 的定义可以证明:D ≤ Σ_{sᵢ>t} vᵢ(sᵢ − t)(D > 0 时),所以理论上总能倒够——唯一的问题是要不要把"全部原料"都倒掉,导致体积为 0。实现时只需判断最终体积是否 > 0 即可。算总偏离 D,按 |sᵢ−t| 排序后从需要的方向贪心倒
D = Σvᵢ(sᵢ−t);若 D > 0 就从"甜度最大"开始倒,若 D < 0 就从"甜度最小"开始倒,每升改变偏离 |sᵢ − t|,倒到偏离清零为止。假设只用两种原料(一高一低)混合出甜度 t
| 方案 | 代码量 | 易错程度 |
|---|---|---|
| 全局贪心 | 约 30 行 | 低 |
| 枚举两两 | 约 45 行 | 高 |
第一行输入 n 和 t,随后 n 行输入每种的体积与甜度。
点按钮开始 →
#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|。所以要改变给定的偏离量,选择 |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) | 输出 | 保留三位小数 |
s > t 的原料);② 用 int 计算(体积可以是小数,必须用 double);③ 忘记保留三位小数(用 %.3f)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 2 | 14.667 | 题面样例 |
1 5 | 1.000 | 唯一原料甜度恰好等于 t,全部可用 |
1 5 | 0.000 | 无法调制:只有一种原料且甜度 ≠ t |
2 2 | 2.000 | 一低一高,各用 1 升混合,平均恰好为 2 |
2 5 | 7.000 | 全部甜度都等于 t,全部可用 |
fabs(x) < 1e-9)。%.3f)。需要存下 n 种的体积与甜度。
✅ 排序是主要开销,任何规模都轻松完成。难点在于把"加权平均等于 t"转化为"总偏离为 0"这个约束。
// 本题的数学核心 // 甜度 = Σ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 判零 | 所有涉及小数的比较 |