【算法日记04】贪心算法实战：从“林黛玉倒茶”彻底顿悟“向上取整”魔法

🌟【算法进阶】贪心算法实战：从“林黛玉倒茶”彻底顿悟“向上取整”魔法

📍 题目背景

题目大意：
林黛玉有NNN只容量不同的茶杯，需要用一个容量为MMM的茶壶去取水。为了招待客人，至少需要斟满KKK杯茶。问：为了让黛玉尽量少跑几趟，最少需要用茶壶取多少次水？

• 输入：茶杯总数NNN，茶壶容量MMM，目标杯数KKK。以及NNN个茶杯的容量数组CCC。
• 输出：最少的取水次数。

💡 核心解题思路：三步绝杀

这道题的本质是一道极其标准的贪心算法（Greedy Algorithm）应用题，外加一个程序设计中极其经典的数学进位陷阱。

第一步：贪心排序（挑软柿子捏）

既然要求“最少跑几趟（最省水）”，且只需要斟满KKK杯，那么我们理所当然应该挑容量最小的KKK个杯子来倒！
操作：直接使用 C++ 的sort()函数对茶杯数组进行从小到大排序。

第二步：精准求和（只算目标）

不要去管所有的NNN个杯子，用一个for循环，只把排在最前面的KKK个杯子的容量加起来，得到总需水量sum。

⚠️ 避坑：多个杯子的容量相加极容易超出int的上限，所以累加器sum务必使用long long！

第三步：计算趟数（跨越物理与数学的鸿沟）

得到总需水量sum和茶壶容量MMM后，如何求趟数？这里隐藏着最大的坑——不能直接用除法！

🧠 终极顿悟：为什么要“向上取整”？

很多新手（包括我）一开始会顺手写出res = sum / m;。在 C++ 里，整数除法是**“向下取整（砍尾巴）”**的。这在物理世界里是极其荒谬的。

🚕 极其生动的“打车理论”：
假设 10 个人去聚餐，一辆车最多坐 4 人。

• 数学算法：10÷4=2.510 \div 4 = 2.510÷4=2.5辆车。
• C++ 整数除法：10 / 4 = 2辆车（最后的 2 个人被丢下了！）。
• 物理世界的现实：剩下的 2 个人，哪怕坐不满一整辆车，你也必须为他们额外再叫一辆完整的车！所以结果必须是3 辆。

倒茶也是一样：
假设最后还剩 1 滴水没倒，林黛玉能只跑“三分之一趟”吗？不行！为了这 1 滴水，她也得拎着茶壶跑一个完整的回合。只要有余数，趟数就必须 +1！

✨ 大牛的 O(1) 魔法公式：
不要再写繁琐的if (sum % m != 0)了，直接套用向上取整公式：
res=sum+M−1Mres = \frac{sum + M - 1}{M}res=Msum+M−1​
在 C++ 代码中即：res = (sum + m - 1) / m;。这个公式完美利用了整数除法的特性，强行把余数顶成新的一趟！

💻 满分 AC 代码 (C++11)

时间复杂度：O(Nlog⁡N)O(N \log N)O(NlogN)（主要耗时在排序上），空间复杂度O(N)O(N)O(N)。

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){intn,m,k;// 严谨读取输入if(!(cin>>n>>m>>k))return0;vector<int>c(n);for(inti=0;i<n;i++){cin>>c[i];}// 1. 贪心起手式：将杯子容量从小到大排好队sort(c.begin(),c.end());// 2. 算水：只收集前 K 个最小茶杯的总需水量 (注意开 long long 防溢出)longlongsum=0;for(inti=0;i<k;i++){sum+=c[i];}// 3. 倒水：施展“向上取整”魔法，计算需要打几次水longlongres=(sum+m-1)/m;/* 等价于老实人写法： long long res = sum / m; if (sum % m != 0) res++; */cout<<res<<endl;return0;}

🏆 总结收获

1. 逻辑解耦：写代码时，切忌把“计算总需水量”和“模拟倒水回合”放在同一个循环里搅和。先算出总目标，再用公式一步求解，逻辑才会无懈可击。
2. 物理思维：只要涉及到“装载、运输、分批次”的问题，永远不要忘记 C++ 除法的“砍尾巴”特性，立刻条件反射出向上取整。
3. 贪心直觉：遇到“最少/最多”且没有复杂状态依赖的题目，第一时间考虑sort排序找局部最优解。