【算法刷题】蓝桥杯林黛玉的茶局贪心算法 向上取整 题目描述与考点题目名称林黛玉的茶局核心问题柜子里有N NN只茶杯容量分别为C 1 , C 2 , … , C N C_1, C_2, \dots, C_NC1​,C2​,…,CN​。有一个容量为M MM的茶壶。要求挑选并斟满至少K KK杯茶求用茶壶最少需要取水的次数。数据规模1 ≤ K ≤ N ≤ 10 3 1 \le K \le N \le 10^31≤K≤N≤1031 ≤ M ≤ 10 3 1 \le M \le 10^31≤M≤1031 ≤ C i ≤ 10 3 1 \le C_i \le 10^31≤Ci​≤103核心考点贪心算法、数组排序、整数向上取整技巧。 核心思路解析1. 贪心策略推导题目要求取水次数最少且只需斟满K KK杯茶无需装满全部N NN杯目标使用的总水量越少取水次数就越少。策略将所有茶杯的容量按从小到大排序优先挑选容量最小的K KK个茶杯进行填充。2. 水量计算与向上取整设这K KK个最小茶杯的容量和为S ∑ i 1 K C i S \sum_{i1}^{K} C_iS∑i1K​Ci​茶壶容量为M MM因此需要取水的次数为⌈ S / M ⌉ \lceil S / M \rceil⌈S/M⌉。常用实现方式分支判断法b sum / m; if (sum % m ! 0) b;公式一步法(sum m - 1) / m竞赛推荐写法。 C 完整 AC 代码#includeiostream#includevector#includealgorithmusingnamespacestd;intmain(){// 快速 I/O 优化ios::sync_with_stdio(false);cin.tie(nullptr);intn,m,k;if(!(cinnmk))return0;vectorintc(n);for(inti0;in;i){cinc[i];}// 1. 贪心从大到小排序优先选择容量最小的 K 个杯子sort(c.begin(),c.end());// 2. 累加前 K 个茶杯的总体积longlongsum0;for(inti0;ik;i){sumc[i];}// 3. 计算取水次数向上取整longlongans(summ-1)/m;coutans\n;return0;}❌ 易错点总结题意理解偏差错以为要把所有N NN个茶杯都加满忽略了只需满足K KK个茶杯的限制。贪心方向反转误选了容量较大的K KK个茶杯导致需要的总水量增加取水次数变多。向下取整陷阱直接使用sum / m进行整除忽略了余数部分也需要额外取水一次的情况。⏱️ 复杂度分析时间复杂度O ( N log ⁡ N ) \mathcal{O}(N \log N)O(NlogN)主要开销在于对N NN个茶杯容量进行排序。在N ≤ 10 3 N \le 10^3N≤103的数据规模下耗时不到 1ms轻松 AC。空间复杂度O ( N ) \mathcal{O}(N)O(N)用于存储茶杯容量信息的vector数组。