题目传送门
解题思路：
非常典型的优化决策类问题，这类题目在信息学竞赛中频繁出现，尤其是在贪心算法和排序策略的应用场景中。我们一起来逐步剖析这个问题，引导你自己找到突破口。
🌟 第一步：理解题意 —— 把现实问题转化为数学模型
我们来重新梳理一下题目中的关键要素：
有 $ n $ 首歌，每首歌有两个属性：
原始大小 $ a_i $
压缩后大小 $ b_i $（且 $ b_i < a_i $）
闪存驱动器容量为 $ m $
所有歌曲都必须放进驱动器（不能丢弃）
可以选择任意子集进行压缩（每首歌要么原样放，要么压缩放）
目标是：使总大小 ≤ m 的前提下，压缩的歌曲数量最少
✅ 注意：如果无论如何都无法满足总大小 ≤ m，则输出 -1
🔍 第二步：观察样例，寻找直觉
来看第一个`
n=4, m=21
[10,8], [7,4], [3,1], [5,4]
如果不压缩任何一首歌，总大小是：
10+7+3+5=25>21→不行10 + 7 + 3 + 5 = 25 > 21 → \text{不行} 10+7+3+5=25>21→不行
所以我们必须压缩一些歌。
但我们的目标是最少压缩几首就能让总大小 ≤ 21。
思考一个问题：
> 压缩一首歌能带来什么？它节省了多少空间？
对第 $ i $ 首歌来说，压缩带来的“收益”是：
节省的空间=ai−bi\text{节省的空间} = a_i - b_i 节省的空间=ai −bi
所以，如果你要通过压缩减少总占用，那么你应该优先压缩那些节省空间最多的歌曲吗？
还是应该考虑别的因素？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
💡 第三步：提出假设并验证
让我们尝试构建一种策略：
假设1：“我应该先压缩节省空间最多的歌”
比如上面的例子中，计算每个歌的节省量：
歌曲 aia_iai bib_ibi 节省 ai−bia_i - b_iai −bi 1 10 8 2 2 7 4 3 3 3 1 2 4 5 4 1
按节省从大到小排序：歌曲2(3) > 歌曲1/3(2) > 歌曲4贪心地压缩节省最多的歌曲，直到总大小 ≤ m，会不会得到最优解？
试一试：
* 初始总大小：25
* 压缩歌曲2 → 新总大小 = 25 - 3 = 22 > 21 ❌ 不够
* 再压缩歌曲1 → 总大小 = 22 - 2 = 20 ≤ 21 ✅ 成功！用了2次压缩
结果是压缩了2首 → 输出2，符合样例！
这说明这个策略可能有效？
但等等……是不是所有情况都成立？
再想想：有没有这样一种情况——某首歌虽然节省空间不多，但它原本就很小，压缩代价低？或者反过来，有一首歌节省很多，但其实没必要优先处理？
换个角度想：
> 我们的问题本质是：在满足总大小 ≤ m 的条件下，最小化压缩次数
这就像是一个带约束的最优化问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
⚙️ 第四步：形式化建模
定义：
* 设集合 $ S $ 是被压缩的歌曲集合
* 总大小为：
∑i∉Sai+∑i∈Sbi=∑i=1nai−∑i∈S(ai−bi)\sum_{i \notin S} a_i + \sum_{i \in S} b_i = \sum_{i=1}^n a_i - \sum_{i \in S}(a_i - b_i) i∈/S∑ ai +i∈S∑ bi =i=1∑n ai −i∈S∑ (ai −bi )
* 要求：\sum a_i - \sum_{i \in S}(a_i - b_i) \leq m \Rightarrow \sum_{i \in S}(a_i_i - m
记 $ T = \sum a_i - m $
> 如果 $ T \leq 0 $，说明不压缩也够用 → 答案是 0
否则，我们需要选一个尽可能小的集合 $ S $，使得这些歌曲的“节省值”之和 ≥ $ T $
🎯 这变成了一个经典的 最小数量覆盖目标值 的问题：
> 给定一组正数 $ d_i = a_i - b_i $，从中选出最少的数量，使其和 ≥ 某个目标值 $ T $
这时候你应该想到：
👉 为了用最少的数量达到目标，应该优先选 $ d_i $ 最大的那些！
这就是贪心思想的核心：单位动作收益越高，越优先执行
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
❓ 第五步：启发式提问（帮你自我探索）
现在，请你思考以下几个问题：
1. 如果所有歌曲都不压缩时总大小已经 ≤ m，答案是多少？
2. 如果即使全部压缩，总大小仍然 > m，该怎么办？如何判断这种情况？
3. 当我们必须压缩若干首歌才能满足容量限制时，为什么“按节省空间从大到小排序”是一种合理的策略？
4. 这种贪心策略会不会失败？是否存在反例？（可以试着构造一个反例来挑战这个想法）
5. 如何高效实现这个过程？时间复杂度要求是 $ O(n \log n) $ 吗？瓶颈在哪里？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
🧩 第六步：分解步骤建议
你可以尝试按照以下逻辑框架编写代码：
1. 计算所有歌曲原始总大小 $ \text{total_a} = \sum a_i $
2. 如果 $ \text{total_a} \leq m $，直接返回 0
3. 计算即使全压缩后的最小可能总大小：$ \text{total_b} = \sum b_i $
* 如果 $ \text{total_b} > m $，则不可能成功 → 返回 -1
4. 否则，需要节省至少 $ \text{need} = \text{total_a} - m $ 字节
5. 构造数组 $ \text{savings}[i] = a_i - b_i $，然后从大到小排序
6. 贪心地选取最大的 savings，累加直到 ≥ need
7. 返回选取的数量
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
🛠️ 提示技巧（信奥常用手法）
* 排序+贪心 是解决此类“最小化操作次数”的常见套路
* 注意数据范围：$ n \leq 10^5 $，所以 $ O(n \log n) $ 可接受
* 注意整数溢出：$ a_i, b_i \leq 10^9 ，，， n \leq 10^5 $，总和可达 $ 10^{14} $，要用 long long！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
✅ 最后总结启发
你现在掌握的信息足够让你动手尝试了。记住：
> 解决难题的关键不是立刻写出代码，而是把问题一步步拆解成可处理的小问题。
试着回答自己：
* 这道题的本质是什么？（最小化压缩次数 vs 最大化节省空间）
* 贪心策略成立的前提是什么？我能证明它的正确性吗？
* 如何设计测试样例来验证我的思路？
不妨自己再设计一两个测试用例，比如：
* 全部压缩也不够 → 应该输出 -1
* 压缩一首就够了 → 输出 1
* 必须压缩两首，但顺序不同会影响结果吗？
通过这些练习，你会更深刻理解算法背后的逻辑。
继续加油！如果你在实现过程中遇到具体困难（比如某个条件判断不对、结果偏差），欢迎回来继续讨论。我可以帮你调试思路，但真正的成长来自于你自己一步一步走过的路。
代码登场：
看完不妨点个赞吧
