硬盘装歌最优压缩策略：贪心选择最大节省量歌曲

这是一个**贪心算法**问题，目标是：在硬盘容量有限的前提下，**最小化压缩的歌曲数量**，使得总大小 ≤ 硬盘容量。 --- ### 🔍 问题分析 - 每首歌有两个大小： - `a_i`：原始大小（未压缩） - `b_i`：压缩后大小（一定更小，因为 `b_i < a_i`） - 压缩一首歌能节省的空间是：`a_i - b_i` - 我们希望**用最少的压缩次数**，让所有歌曲总大小 ≤ `m` #### ✅ 思路： 1. **先假设全部不压缩**，计算总大小 `sum(a_i)`： - 如果 `sum(a_i) ≤ m` → 不需要压缩，答案是 `0` 2. **如果超了**，我们需要压缩一些歌来“省空间” - 每压缩一首歌 `i`，节省 `a_i - b_i` 字节 - 要使压缩数量最少 → 应优先压缩**节省空间最多**的那些歌（贪心！） 所以策略是： - 计算每首歌的节省量 `save_i = a_i - b_i` - 按 `save_i` **从大到小排序** - 依次压缩，直到总大小 ≤ `m` - 统计压缩了几首 ⚠️ 注意边界：如果即使**全部压缩**（即全用 `b_i`）总和仍 > `m`，输出 `-1` --- ### ✅ 步骤（算法流程） 1. 读入 `n`, `m` 2. 读入 `n` 对 `(a_i, b_i)` 3. 计算 `total_a = sum(a_i)`, `total_b = sum(b_i)` 4. 若 `total_a ≤ m` → 输出 `0` 5. 若 `total_b > m` → 输出 `-1` 6. 否则： - 构造数组 `saves = [a_i - b_i for each i]` - 降序排序 `saves` - 初始化 `compressed = 0`, `current_saved = 0` - 遍历 `saves`，累加 `current_saved += saves[i]`，`compressed++` - 直到 `total_a - current_saved ≤ m` → break 7. 输出 `compressed` --- ### 🧮 样例验证（题目给的） 输入： ``` 4 21 10 8 → save = 2 7 4 → save = 3 3 1 → save = 2 5 4 → save = 1 ``` - `total_a = 10 + 7 + 3 + 5 = 25` - `m = 21` → 需要至少节省 `25 - 21 = 4` 字节 - `saves = [2, 3, 2, 1]` → 排序后 `[3, 2, 2, 1]` - 压缩第1首（save=3）→ 已省3，还需1 - 压缩第2首（save=2）→ 累计省5 ≥ 4 → ✅ - 所以答案是 `2` ✔️ 匹配样例输出。 --- ### 💻 Python 实现（高效，O(n log n)） ```python import sys def main(): data = sys.stdin.read().split() if not data: return n = int(data[0]) m = int(data[1]) songs = [] idx = 2 total_a = 0 total_b = 0 for _ in range(n): a = int(data[idx]) b = int(data[idx + 1]) idx += 2 songs.append((a, b)) total_a += a total_b += b # 情况1：全不压缩就够 if total_a <= m: print(0) return # 情况2：全压缩也不够 if total_b > m: print(-1) return # 计算每首歌压缩能节省的空间 saves = [a - b for a, b in songs] saves.sort(reverse=True) # 从大到小 need_save = total_a - m # 至少要节省这么多 saved = 0 count = 0 for s in saves: saved += s count += 1 if saved >= need_save: break print(count) if __name__ == "__main__": main() ``` --- ### ⚙️ 复杂度分析 - 时间：`O(n log n)`（主要是排序） - 空间：`O(n)` 适用于 `n ≤ 10^5`，完全满足题目要求。 --- ### 💡 开发建议（进阶思考） - 可用堆（`heapq`）替代排序，若只取 top-k，但本题最坏仍需全部扫描，排序更直观。 - 注意整数溢出？Python 自动处理，但 C++/Java 需用 `long long` / `long` - 输入量大时，推荐用 `sys.stdin.read()` 加速（如上） - 可增加输入校验（如 `bi < ai`），但题目已保证 --- ######[AI写代码神器 | 1236点数解答 | 2026-03-18 12:21:54]