RoundPrices取整难题精讲：airbnb题库中贪心策略的完整解法
【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb
RoundPrices（价格取整）是 airbnb 面试题库（gh_mirrors/ai/airbnb）中的一道经典算法题：把一组带小数的房价取整后，还要保证取整结果的总和等于总和的取整。本文带你完整拆解这道题背后的贪心策略，以及题库中两套解法的实现思路。
1. RoundPrices取整问题是什么？
题目场景很贴近现实：Airbnb 上每个房源的房价都是带小数的价格（比如 3.7 美元），财务要求把每个价格都取成整数，但所有价格取整后的总和，必须等于原总和四舍五入后的值。
用一个例子说明：
| 原始价格 | 1.2 | 2.3 | 3.4 |
|---|---|---|---|
| 原总和 | 6.9 → 取整为7 | ||
| ❌ 各自四舍五入 | 1 | 2 | 3 |
| 取整后总和 | 6 ≠ 7 |
单独取整会让总和"少 1"，这就是难题所在：必须在多个数之间重新分配取整误差。
2. 为什么"各自先四舍五入"一定会失败？
四舍五入是"局部最优"：每个数各自选最近的整数，但合起来总和却可能偏离目标值 1 甚至更多。
- 每个数最多差 0.5，n 个数累积误差最多可达 n/2；
- 题目强制要求总和精确等于
round(总和)，因此必须有一个全局调整机制。
这正是贪心算法的用武之地：把"需要补上（或减去）的 1"分配给调整代价最小的数。💡
3. 贪心解法一：先全向下取整，按"最小代价"分配向上取整名额
题库中第一套解法Solution的思路（源码：RoundPrices.java）：
- 全部向下取整（floor），记下整数部分之和
floorSum； - 计算需要向上取整的名额：
diff = round(总和) - floorSum； - 对每个数计算"向上取整的代价"，即它到天花板的距离（
ceil - 原值）； - 贪心选择：把
diff个名额优先分配给代价最小的数（离天花板最近的最先被取整上去），其余保持向下取整。
以{1.2, 3.7, 2.3, 4.8}为例：
| 原值 | 向下取整 | 到天花板的距离 | 处理 |
|---|---|---|---|
| 4.8 | 4 | 0.2 | ✅ 向上取整 → 5 |
| 3.7 | 3 | 0.3 | ✅ 向上取整 → 4 |
| 2.3 | 2 | 0.7 | 保持 2 |
| 1.2 | 1 | 0.8 | 保持 1 |
floorSum = 10，round(12.0) = 12，diff = 2，取代价最小的 2 个数向上取整，得到总和恰好为 12。按代价升序输出结果为[5, 4, 2, 1]。
⚠️ 注意：该解法按"取整代价"重排了输出顺序，不保持输入原顺序，面试中需要主动向考官说明这一点。
4. 贪心解法二：先四舍五入，按小数部分调整
第二套解法Solution_2（源码：RoundPrices.java）更符合日常习惯，且保持输入顺序：
- 每个数先按常规四舍五入，得到初始结果与总和
roundSum； - 若
roundSum < round(总和)：把"最该进位"的数（小数部分最大的、且原本被舍去的数）改成向上取整，补齐差额； - 若
roundSum > round(总和)：把"最不该进位"的数（小数部分最小的、且原本被进位的数）改回向下取整，抵消差额； - 两者相等则直接返回。
仍以{1.2, 3.7, 2.3, 4.8}验证：各自四舍五入得1+4+2+5 = 12，恰好等于round(12.0)，直接返回[1, 4, 2, 5]。
两种贪心视角对比：
| 对比项 | 解法一（floor + 分配名额） | 解法二（round + 小数调整） |
|---|---|---|
| 贪心依据 | 到天花板距离最小 | 小数部分最"冤枉" |
| 输出顺序 | 重排 | 保持原序 ✅ |
| 实现复杂度 | 低 | 中（需处理双向调整） |
| 面试推荐 | 快速说清思路 | 工程上更实用 |
5. 复杂度分析与边界情况
- 时间复杂度：排序主导，O(n log n)；
- 空间复杂度：O(n)，用于保存每个数的辅助信息（取值 + 小数部分/取整代价 + 下标）。
题库单元测试（RoundPrices.java）覆盖了这些边界，值得留意：
| 边界场景 | 示例 | 要点 |
|---|---|---|
| 负数 | -0.4 | 向下取整要取到-1方向，floor/ceil语义不能混淆 |
| 整数价格 | 4.0 | 小数部分为 0，不参与调整 |
| 差额为 0 | 各数取整和已吻合 | 解法二直接短路返回 |
6. 源码位置与本地运行
相关模块路径：
- 取整难题源码（含两套解法与单元测试）：src/main/java/round_prices/RoundPrices.java
- 题库题目清单与说明：README.md
- 公共工具类（其他题目共用）：src/main/java/common/
项目基于 Gradle 构建，测试使用 JUnit。本地克隆后执行即可运行 RoundPrices 的全部测试用例：
git clone https://gitcode.com/gh_mirrors/ai/airbnb cd airbnb ./gradlew test7. 总结
RoundPrices 取整题考察的核心不是取整本身，而是误差的贪心分配：
- 先算出"全局差额"（目标总和 - 初始取整总和）；
- 按代价从小到大（或小数部分从大到小）逐个补齐差额；
- 注意负数、整数等边界，并注意是否要保持输入顺序。
掌握这个"先取整、再按最小代价调整"的贪心模板，类似的公平取整、预算分配、投票配额类问题都能快速迁移解决。🚀
【免费下载链接】airbnb项目地址: https://gitcode.com/gh_mirrors/ai/airbnb
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
