1. 题目到底在考你什么GESP五级最容易漏的二分思维先说结论这道luogu-P1843奶牛晒衣服表面是一道“模拟题”只要你按分钟去推思路貌似通顺但实际一交就是TLE。真正要过的关卡是你有没有建立“用二分答案把过程模拟变成结果判定”的思维习惯。而这恰恰是GESP五级大纲里反复强调、但很多同学平时练得最少的一块。我先带你重新读一遍题面看看它到底在说什么。有N件衣服每件衣服含水量是a[i]单位我习惯叫“水分单位”。每件衣服每分钟会自然蒸发1个单位水分。另外有一台烘干机每分钟最多能让一件衣服额外减少K个单位水分也就是烘干机作用的那件衣服这一分钟总共减少K 1个单位水分没被烘干机作用的衣服只减少1个单位。问最少需要多少分钟能让所有衣服含水量都降到0以下含0请注意几个坑人的细节烘干机在同一分钟只能作用于一件衣服不是多件同时烘。自然蒸发是所有衣服同时在进行的不因烘干机而暂停。含水量降到0以后就算干了继续吹风也不会变成负数题目也不关心负数。水量是整数但答案不一定是整数你最后要输出的是“整数分钟数”。很多第一次做这题的同学第一反应是贪心每次把当前含水量最大的那件衣服拿去烘干模拟每一分钟。这个思路本身没有错而且小数据下完全正确。但题目数据范围显示衣服数量N和含水量都可能到十万甚至更大逐分钟模拟的复杂度是O(答案 × N)答案一旦上万甚至百万基本必挂。那为什么“每次烘含水量最大的”这个贪心策略是合理的因为烘干机每分钟只能服务一件衣服而自然蒸发对每件衣服是等速的所以想要让“最后干的那件衣服”尽可能早干每分种就应该把烘干资源给最湿的那件。这个逻辑叫“让短板尽快变长”不过程序上直接模拟它需要维护一个动态最大值的序列每轮都要找最大堆可以做但循环次数本身可能太大整体还是会TLE。这里就引出一个关键思维转变我们不一定非要精确模拟每一分钟发生了什么而是可以“猜测一个总时间T然后判断T分钟内能不能烘干所有衣服”。猜得准不准用二分来找。这种“把最优化问题转成判定问题”的手法就是二分答案。我在给准备GESP五级的孩子讲这题时总是先让他们自己在纸上写一版暴力模拟亲眼看看它跑大数据有多慢再引出二分答案。因为只有当你真正撞过TLE的墙你才会理解判定函数check()为什么是这题的核心而不是记住一个模板就完事。2. 从模拟思维切到判定思维二分答案的骨架长什么样二分答案的基本套路是这样如果题目要求“最小化某个时间T”而且存在一个单调性——T越大越容易满足条件T越小越难满足条件——那么我们就可以在答案的可能范围里二分T每次用check(T)判断“T分钟够不够”然后根据判断结果缩小范围。具体到这题单调性是显而易见的如果你有更多时间干燥当然更容易完成时间少了就很难。所以我们可以二分“所需分钟数”。那答案的上界怎么定最简单也最稳的一种做法是取所有衣服中含水量的最大值。因为就算没有烘干机只有自然蒸发最多也就是这么多分钟全部干透。逻辑上没有任何一件衣服需要比“全部靠自然蒸发”更长的时间所以这个上界一定合法。下界自然是0也可以从1开始个人习惯从0或1都行不影响正确性后面我会说判断细节。二分框架如下int l 0, r maxWater; // 上界取最大含水量 while (l r) { int mid (l r) / 2; if (check(mid)) { r mid; // mid分钟够用尝试更少时间 } else { l mid 1; // mid分钟不够必须更多时间 } } cout l endl;这里的check(mid)表示在mid分钟内能不能让所有衣服都干。可能有人问为什么不直接取平均含水量之类的更紧上界取最大含水量是最安全、最不容易出错的而且二分的范围大小对性能影响是log级别的没必要在这里做微优化。我见过有的同学为了“让二分更快”把上界设成所有衣服含水量总和结果逻辑也没错但完全没有必要。二分答案最怕的不是范围大而是上界设置不合理导致漏掉合法答案。好框架有了真正决定对错的是check函数。这个函数怎么设计直接决定了你能不能AC这道题也是GESP五级考试里判分的关键。3. check函数的设计一个细节就能卡掉半壁江山你现在有了一个猜测的时间T也就是mid需要判断T分钟内所有衣服能否全干。先想最简单的判断思路对每件衣服如果它的含水量a[i]小于等于T那没问题靠自然蒸发T分钟就干了烘干机完全不用管它。如果a[i]大于T说明光靠自然蒸发不够需要额外烘干。那么“不够的部分”是多少是a[i] - T。这部分水分只能靠烘干机来补而烘干机每分钟最多能额外去掉K个单位水分。有的同学直接写需要 a[i] - T 除以 K 分钟向上取整。这里就埋着一个天坑“a[i] - T”部分并不等于烘干机需要烘掉的总量里能被K整除的数学关系因为烘干机作用在一件衣服上的那一分钟同时自然蒸发也在发生你还得考虑烘干机“额外”贡献和自然蒸发“叠加”带来的效率。我们换个更严谨的建模方式。设某件衣服初始含水量为a[i]。如果烘干机在它的身上一共被使用了x分钟这x分钟不需要连续可以分散那么这件衣服在这T分钟里有x分钟享受K1的脱水速率有T - x分钟只享受自然蒸发的1脱水速率。所以它总共减少的水分是x * (K 1) (T - x) * 1 T K * x要让这件衣服干即T K * x a[i]也就是说需要烘干机在它身上投入的分钟数至少是x (a[i] - T) / K注意这个公式里是用K而不是K1。为什么因为在刚才的推导里(K1)倍的x分钟贡献里已经包含了x分钟的自然蒸发和剩下T - x分钟的自然蒸发合起来是整个T分钟的自然蒸发多出来的纯烘干贡献就是K * x。所以我们只需让额外贡献K * x补足自然蒸发不够的那部分也就是a[i] - T。这个“T K * x a[i]”的公式是本题最核心的数学模型。我见过不少题解直接写“每件衣服需要ceil((a[i] - T) / K)次烘干”如果你理解了上面的推导就知道这个式子是对的但前提是你把“烘干机每分钟额外烘干K”和“自然蒸发1”分清楚千万别在check里错误地写成a[i] - T除以K1。接下来你只要把每件衣服需要的烘干机分钟数累加起来得到一个总数needbool check(long long T) { long long need 0; for (int i 1; i n; i) { if (a[i] T) { need (a[i] - T k - 1) / k; // 向上取整 } } return need T; // 烘干机的总可用分钟数就是T分钟 }这里最后的判断 need T 是决定性的一步。因为烘干机一共只有T分钟每分钟作用一件衣服而你把所有衣服需要的烘干时间加起来是need分钟只有need不超过T才说明烘干机忙得过来。注意这个判断天然保证了“烘干机同一时间只能服务一件衣服”的约束因为你只是把每个需求累加并没有让它们并行。这个check函数的写法是这道题唯一AC路径。我见过有同学把need和n比较、把need和某个其他东西比较都属于没有真正理解约束条件。4. 边界条件与ceil取舍为什么这两份AC代码写法不同但都对知道了check函数看起来不难但真正写的时候有三个边界细节能决定你是AC还是WA。第一个边界是ceil取整的写法。你要计算(a[i] - T) / K向上取整。整数向上取整的通用写法是(a[i] - T k - 1) / k这个写法的前提是(a[i] - T)和k都大于0。如果a[i] - T是负数或0说明不需要烘干直接跳过所以我一般先判断if (a[i] T)再累加。有的同学图省事不管a[i]和T的关系直接算会用max(0, ...)包一层也可以但一定要小心C整数除法是向零截断还是向下取整——对于正数来说两者一样但概念上要知道自己在做什么。第二个边界是二分上下界的开闭。我上面写的模板是while (l r) { int mid (l r) / 2; if (check(mid)) r mid; else l mid 1; }这个模板的特点是check(mid)为真时答案可能是mid或比mid更小所以压缩右边界到mid为假时答案一定比mid大所以左边界跳到mid 1。这个写法天然要求check函数对“T分钟够不够”返回布尔值且有单调性。起始下界我建议设0而不是1因为有一种特殊情况——所有衣服含水量都是0那0分钟就全部干完下界设0直接输出0逻辑更干净。如果你设1遇到全0数据二分会把它逼到1输出1WA。一般题目不会那么毒但严谨起见从0开始更稳。第三个边界也是很多第一次AC之后又回头纠结的问题为什么有的题解把二分的判断条件写成(r - l 1)然后用mid (l r) / 2最后输出r实际上两种写法等价区别只在于循环不变量的定义。我个人推荐“闭区间收缩”写法因为它的终止条件是l r答案就是l不需要额外考虑“l和r哪个是答案”。如果你从1开始、用开区间写法最后输出r也别奇怪关键是你在考场上一套逻辑走到底别混着用。这里额外提醒一个精度问题。有的同学看到a[i] - T要除以K就想着转成double用ceil函数比如need (int)ceil((a[i] - T) * 1.0 / k);这种方式在小数据下没错但在大数据下引入浮点误差风险而且比整数写法慢。GESP五级考试里我强烈建议全程用整数运算。不是因为double一定挂而是你没必要在能精确整数解决的问题上引入额外的出错维度。我见过真实案例有人因为浮点误差在边界数据上WA了两次换整数写法一遍过。再补充一个数据类型问题。N和a[i]的范围如果到1e5K也可能到1e5极端情况下need用int会溢出吗我们算一下如果N1e5每件衣服含水量都是1e5T最大也是1e5K最小是1那么need最大约等于 N * (1e5 - 1)大约是1e10超出int范围。所以need必须用long long。这是这道题里最容易忽略的“不是算法难而是类型爆了”的典型。5. 贪心模拟为何必挂 一个你可能没注意的数学等价我前面反复说贪心模拟会TLE但你有没有想过它到底慢在哪假设答案需要ans分钟每轮要从N件衣服里找最大值如果用堆找最大值是O(logN)堆更新也是O(logN)整体是O(ans * logN)。如果ans达到10^7量级这个复杂度就是10^7 * log(1e5)大约1.2亿次操作在C里勉强能跑但如果N也很大且ans更大就非常危险。而二分答案的复杂度是O(log(maxWater) * N)maxWater哪怕到1e9log也就31次乘以N1e5只有310万次操作差距是数量级的。更值得注意的是贪心模拟还存在一个精确性问题在极端数据下贪心策略“每轮烘当前最大”虽然直觉正确但也需要证明没有更优的调度方式。如果每个时刻只能服务一个对象且所有对象的“自然流逝”速率相同那么这个贪心确实是最优的。可一旦你面对的题目里自然蒸发速率不一样比如不同衣服有不同蒸发率贪心就会失效。GESP五级以后的题目很喜欢在这种地方做文章所以培养“从判定视角看问题”的能力比背一个题的解更重要。我再展开一下那个数学等价的推导让大家彻底吃透check函数。对于每件衣服a[i]假设在T分钟内烘干机碰过它x分钟这x分钟里它每分钟减少K 1烘干机额外贡献K自然蒸发贡献1其余T - x分钟里它每分钟减少1纯自然蒸发总减少量 x * (K 1) (T - x) * 1 T Kx要求总减少量 ≥ a[i]即T Kx ≥ a[i]所以x ≥ (a[i] - T) / K。这里的x是一个“理论所需烘干分钟数”它可以是小数但你实际安排烘干机的分钟数是整数因此要对每一项向上取整。这个向上取整非常关键你不能把0.5分钟拆成两个0.25分钟烘干机最小时间单位是1分钟所以任何一件衣服只要理论需要0.1分钟你也必须给它整1分钟。在check函数里我们把每件衣服的所需烘干分钟数累加得到need。如果need ≤ T就说明烘干机能在T分钟内排满这些活答案是可行的。如果need T说明即使烘干机满负荷运转T分钟也不够答案不可行。我之所以说得这么细是因为这道题在GESP五级真题里具有很高的代表性它看起来像贪心模拟实际上考的是二分答案 数学建模 整数取整三个知识点任何一个环节没打通考场上的表现都会打折扣。6. 从P1843到GESP五级考场的三点推广经验刷完这道题我建议你顺手做三件“举一反三”的事因为它们才是这题真正想留给你的东西。第一留意凡是“求最小时间”“求最少次数”且答案具有单调性的题目都可以优先想二分答案。比如经典的“切绳子”问题、木材加工问题、跳石头问题核心都是先写一个check函数再二分答案。GESP五级很喜欢把这种“二分答案 贪心判定”的组合藏在模拟题的外壳下如果你只会模拟就会很吃亏。第二写check函数时一定要先想清楚“约束条件”是什么。这道题的约束有两个一是每件衣服需要足够的脱水总量二是烘干机总服务时间是T分钟。check函数本质上是在回答“给定T这两个约束能不能同时满足”。很多二分答案题的check函数其实就是在做约束校验一旦你把约束想清楚代码往往非常简单。第三复习一下整数向上取整的写法最好练到一眼就能写对。除了(a b - 1) / b这个公式你还可以考虑a / b (a % b ! 0)的写法效果一样。我个人的偏好是第一种因为它短。但在考试时如果你担心整个人写晕第二种写法更不容易出边界错误。选哪种都行关键是你要确实理解为什么这两种写法等价而不是靠记忆。最后说点考场上的操作建议。GESP五级是机考环境一般是常见的C编译器不会掏太偏的库。你只需要用到iostream、algorithm、vector这些基础头文件不需要STL高级容器。如果你平常用VSCode写C提前把C环境配好熟悉一下单文件编译运行流程别在考场上花时间折腾编译器配置。至于网上常见的“microsoft visual C redistributable”之类的问题和竞赛环境没什么关系不需要理会。还有一个小习惯写完代码先自己造几组边界数据测试比如只有一件衣服K1所有衣服含水量都为0K特别大比如100000远大于含水量含水量全相等N1含水量等于1K1这几组数据能帮你快速验证二分上下界有没有写错、check函数有没有逻辑漏洞。我在带队练习时总跟学生说AC的代码不是一次写对的是测出来的。你省了测试的时间就要花更多时间在罚时上。这道P1843奶牛晒衣服如果你能独立把贪心模拟的思路演进到二分答案并且把check函数写得又短又准那GESP五级里的二分答案类题目你基本就过关了。后面再遇到类似题目你会发现核心思想都是同一套猜答案、验可行性、缩范围、输出结果。顺着这个思路去练越练越顺。
P1843奶牛晒衣服：二分答案与check函数实战解析
1. 题目到底在考你什么GESP五级最容易漏的二分思维先说结论这道luogu-P1843奶牛晒衣服表面是一道“模拟题”只要你按分钟去推思路貌似通顺但实际一交就是TLE。真正要过的关卡是你有没有建立“用二分答案把过程模拟变成结果判定”的思维习惯。而这恰恰是GESP五级大纲里反复强调、但很多同学平时练得最少的一块。我先带你重新读一遍题面看看它到底在说什么。有N件衣服每件衣服含水量是a[i]单位我习惯叫“水分单位”。每件衣服每分钟会自然蒸发1个单位水分。另外有一台烘干机每分钟最多能让一件衣服额外减少K个单位水分也就是烘干机作用的那件衣服这一分钟总共减少K 1个单位水分没被烘干机作用的衣服只减少1个单位。问最少需要多少分钟能让所有衣服含水量都降到0以下含0请注意几个坑人的细节烘干机在同一分钟只能作用于一件衣服不是多件同时烘。自然蒸发是所有衣服同时在进行的不因烘干机而暂停。含水量降到0以后就算干了继续吹风也不会变成负数题目也不关心负数。水量是整数但答案不一定是整数你最后要输出的是“整数分钟数”。很多第一次做这题的同学第一反应是贪心每次把当前含水量最大的那件衣服拿去烘干模拟每一分钟。这个思路本身没有错而且小数据下完全正确。但题目数据范围显示衣服数量N和含水量都可能到十万甚至更大逐分钟模拟的复杂度是O(答案 × N)答案一旦上万甚至百万基本必挂。那为什么“每次烘含水量最大的”这个贪心策略是合理的因为烘干机每分钟只能服务一件衣服而自然蒸发对每件衣服是等速的所以想要让“最后干的那件衣服”尽可能早干每分种就应该把烘干资源给最湿的那件。这个逻辑叫“让短板尽快变长”不过程序上直接模拟它需要维护一个动态最大值的序列每轮都要找最大堆可以做但循环次数本身可能太大整体还是会TLE。这里就引出一个关键思维转变我们不一定非要精确模拟每一分钟发生了什么而是可以“猜测一个总时间T然后判断T分钟内能不能烘干所有衣服”。猜得准不准用二分来找。这种“把最优化问题转成判定问题”的手法就是二分答案。我在给准备GESP五级的孩子讲这题时总是先让他们自己在纸上写一版暴力模拟亲眼看看它跑大数据有多慢再引出二分答案。因为只有当你真正撞过TLE的墙你才会理解判定函数check()为什么是这题的核心而不是记住一个模板就完事。2. 从模拟思维切到判定思维二分答案的骨架长什么样二分答案的基本套路是这样如果题目要求“最小化某个时间T”而且存在一个单调性——T越大越容易满足条件T越小越难满足条件——那么我们就可以在答案的可能范围里二分T每次用check(T)判断“T分钟够不够”然后根据判断结果缩小范围。具体到这题单调性是显而易见的如果你有更多时间干燥当然更容易完成时间少了就很难。所以我们可以二分“所需分钟数”。那答案的上界怎么定最简单也最稳的一种做法是取所有衣服中含水量的最大值。因为就算没有烘干机只有自然蒸发最多也就是这么多分钟全部干透。逻辑上没有任何一件衣服需要比“全部靠自然蒸发”更长的时间所以这个上界一定合法。下界自然是0也可以从1开始个人习惯从0或1都行不影响正确性后面我会说判断细节。二分框架如下int l 0, r maxWater; // 上界取最大含水量 while (l r) { int mid (l r) / 2; if (check(mid)) { r mid; // mid分钟够用尝试更少时间 } else { l mid 1; // mid分钟不够必须更多时间 } } cout l endl;这里的check(mid)表示在mid分钟内能不能让所有衣服都干。可能有人问为什么不直接取平均含水量之类的更紧上界取最大含水量是最安全、最不容易出错的而且二分的范围大小对性能影响是log级别的没必要在这里做微优化。我见过有的同学为了“让二分更快”把上界设成所有衣服含水量总和结果逻辑也没错但完全没有必要。二分答案最怕的不是范围大而是上界设置不合理导致漏掉合法答案。好框架有了真正决定对错的是check函数。这个函数怎么设计直接决定了你能不能AC这道题也是GESP五级考试里判分的关键。3. check函数的设计一个细节就能卡掉半壁江山你现在有了一个猜测的时间T也就是mid需要判断T分钟内所有衣服能否全干。先想最简单的判断思路对每件衣服如果它的含水量a[i]小于等于T那没问题靠自然蒸发T分钟就干了烘干机完全不用管它。如果a[i]大于T说明光靠自然蒸发不够需要额外烘干。那么“不够的部分”是多少是a[i] - T。这部分水分只能靠烘干机来补而烘干机每分钟最多能额外去掉K个单位水分。有的同学直接写需要 a[i] - T 除以 K 分钟向上取整。这里就埋着一个天坑“a[i] - T”部分并不等于烘干机需要烘掉的总量里能被K整除的数学关系因为烘干机作用在一件衣服上的那一分钟同时自然蒸发也在发生你还得考虑烘干机“额外”贡献和自然蒸发“叠加”带来的效率。我们换个更严谨的建模方式。设某件衣服初始含水量为a[i]。如果烘干机在它的身上一共被使用了x分钟这x分钟不需要连续可以分散那么这件衣服在这T分钟里有x分钟享受K1的脱水速率有T - x分钟只享受自然蒸发的1脱水速率。所以它总共减少的水分是x * (K 1) (T - x) * 1 T K * x要让这件衣服干即T K * x a[i]也就是说需要烘干机在它身上投入的分钟数至少是x (a[i] - T) / K注意这个公式里是用K而不是K1。为什么因为在刚才的推导里(K1)倍的x分钟贡献里已经包含了x分钟的自然蒸发和剩下T - x分钟的自然蒸发合起来是整个T分钟的自然蒸发多出来的纯烘干贡献就是K * x。所以我们只需让额外贡献K * x补足自然蒸发不够的那部分也就是a[i] - T。这个“T K * x a[i]”的公式是本题最核心的数学模型。我见过不少题解直接写“每件衣服需要ceil((a[i] - T) / K)次烘干”如果你理解了上面的推导就知道这个式子是对的但前提是你把“烘干机每分钟额外烘干K”和“自然蒸发1”分清楚千万别在check里错误地写成a[i] - T除以K1。接下来你只要把每件衣服需要的烘干机分钟数累加起来得到一个总数needbool check(long long T) { long long need 0; for (int i 1; i n; i) { if (a[i] T) { need (a[i] - T k - 1) / k; // 向上取整 } } return need T; // 烘干机的总可用分钟数就是T分钟 }这里最后的判断 need T 是决定性的一步。因为烘干机一共只有T分钟每分钟作用一件衣服而你把所有衣服需要的烘干时间加起来是need分钟只有need不超过T才说明烘干机忙得过来。注意这个判断天然保证了“烘干机同一时间只能服务一件衣服”的约束因为你只是把每个需求累加并没有让它们并行。这个check函数的写法是这道题唯一AC路径。我见过有同学把need和n比较、把need和某个其他东西比较都属于没有真正理解约束条件。4. 边界条件与ceil取舍为什么这两份AC代码写法不同但都对知道了check函数看起来不难但真正写的时候有三个边界细节能决定你是AC还是WA。第一个边界是ceil取整的写法。你要计算(a[i] - T) / K向上取整。整数向上取整的通用写法是(a[i] - T k - 1) / k这个写法的前提是(a[i] - T)和k都大于0。如果a[i] - T是负数或0说明不需要烘干直接跳过所以我一般先判断if (a[i] T)再累加。有的同学图省事不管a[i]和T的关系直接算会用max(0, ...)包一层也可以但一定要小心C整数除法是向零截断还是向下取整——对于正数来说两者一样但概念上要知道自己在做什么。第二个边界是二分上下界的开闭。我上面写的模板是while (l r) { int mid (l r) / 2; if (check(mid)) r mid; else l mid 1; }这个模板的特点是check(mid)为真时答案可能是mid或比mid更小所以压缩右边界到mid为假时答案一定比mid大所以左边界跳到mid 1。这个写法天然要求check函数对“T分钟够不够”返回布尔值且有单调性。起始下界我建议设0而不是1因为有一种特殊情况——所有衣服含水量都是0那0分钟就全部干完下界设0直接输出0逻辑更干净。如果你设1遇到全0数据二分会把它逼到1输出1WA。一般题目不会那么毒但严谨起见从0开始更稳。第三个边界也是很多第一次AC之后又回头纠结的问题为什么有的题解把二分的判断条件写成(r - l 1)然后用mid (l r) / 2最后输出r实际上两种写法等价区别只在于循环不变量的定义。我个人推荐“闭区间收缩”写法因为它的终止条件是l r答案就是l不需要额外考虑“l和r哪个是答案”。如果你从1开始、用开区间写法最后输出r也别奇怪关键是你在考场上一套逻辑走到底别混着用。这里额外提醒一个精度问题。有的同学看到a[i] - T要除以K就想着转成double用ceil函数比如need (int)ceil((a[i] - T) * 1.0 / k);这种方式在小数据下没错但在大数据下引入浮点误差风险而且比整数写法慢。GESP五级考试里我强烈建议全程用整数运算。不是因为double一定挂而是你没必要在能精确整数解决的问题上引入额外的出错维度。我见过真实案例有人因为浮点误差在边界数据上WA了两次换整数写法一遍过。再补充一个数据类型问题。N和a[i]的范围如果到1e5K也可能到1e5极端情况下need用int会溢出吗我们算一下如果N1e5每件衣服含水量都是1e5T最大也是1e5K最小是1那么need最大约等于 N * (1e5 - 1)大约是1e10超出int范围。所以need必须用long long。这是这道题里最容易忽略的“不是算法难而是类型爆了”的典型。5. 贪心模拟为何必挂 一个你可能没注意的数学等价我前面反复说贪心模拟会TLE但你有没有想过它到底慢在哪假设答案需要ans分钟每轮要从N件衣服里找最大值如果用堆找最大值是O(logN)堆更新也是O(logN)整体是O(ans * logN)。如果ans达到10^7量级这个复杂度就是10^7 * log(1e5)大约1.2亿次操作在C里勉强能跑但如果N也很大且ans更大就非常危险。而二分答案的复杂度是O(log(maxWater) * N)maxWater哪怕到1e9log也就31次乘以N1e5只有310万次操作差距是数量级的。更值得注意的是贪心模拟还存在一个精确性问题在极端数据下贪心策略“每轮烘当前最大”虽然直觉正确但也需要证明没有更优的调度方式。如果每个时刻只能服务一个对象且所有对象的“自然流逝”速率相同那么这个贪心确实是最优的。可一旦你面对的题目里自然蒸发速率不一样比如不同衣服有不同蒸发率贪心就会失效。GESP五级以后的题目很喜欢在这种地方做文章所以培养“从判定视角看问题”的能力比背一个题的解更重要。我再展开一下那个数学等价的推导让大家彻底吃透check函数。对于每件衣服a[i]假设在T分钟内烘干机碰过它x分钟这x分钟里它每分钟减少K 1烘干机额外贡献K自然蒸发贡献1其余T - x分钟里它每分钟减少1纯自然蒸发总减少量 x * (K 1) (T - x) * 1 T Kx要求总减少量 ≥ a[i]即T Kx ≥ a[i]所以x ≥ (a[i] - T) / K。这里的x是一个“理论所需烘干分钟数”它可以是小数但你实际安排烘干机的分钟数是整数因此要对每一项向上取整。这个向上取整非常关键你不能把0.5分钟拆成两个0.25分钟烘干机最小时间单位是1分钟所以任何一件衣服只要理论需要0.1分钟你也必须给它整1分钟。在check函数里我们把每件衣服的所需烘干分钟数累加得到need。如果need ≤ T就说明烘干机能在T分钟内排满这些活答案是可行的。如果need T说明即使烘干机满负荷运转T分钟也不够答案不可行。我之所以说得这么细是因为这道题在GESP五级真题里具有很高的代表性它看起来像贪心模拟实际上考的是二分答案 数学建模 整数取整三个知识点任何一个环节没打通考场上的表现都会打折扣。6. 从P1843到GESP五级考场的三点推广经验刷完这道题我建议你顺手做三件“举一反三”的事因为它们才是这题真正想留给你的东西。第一留意凡是“求最小时间”“求最少次数”且答案具有单调性的题目都可以优先想二分答案。比如经典的“切绳子”问题、木材加工问题、跳石头问题核心都是先写一个check函数再二分答案。GESP五级很喜欢把这种“二分答案 贪心判定”的组合藏在模拟题的外壳下如果你只会模拟就会很吃亏。第二写check函数时一定要先想清楚“约束条件”是什么。这道题的约束有两个一是每件衣服需要足够的脱水总量二是烘干机总服务时间是T分钟。check函数本质上是在回答“给定T这两个约束能不能同时满足”。很多二分答案题的check函数其实就是在做约束校验一旦你把约束想清楚代码往往非常简单。第三复习一下整数向上取整的写法最好练到一眼就能写对。除了(a b - 1) / b这个公式你还可以考虑a / b (a % b ! 0)的写法效果一样。我个人的偏好是第一种因为它短。但在考试时如果你担心整个人写晕第二种写法更不容易出边界错误。选哪种都行关键是你要确实理解为什么这两种写法等价而不是靠记忆。最后说点考场上的操作建议。GESP五级是机考环境一般是常见的C编译器不会掏太偏的库。你只需要用到iostream、algorithm、vector这些基础头文件不需要STL高级容器。如果你平常用VSCode写C提前把C环境配好熟悉一下单文件编译运行流程别在考场上花时间折腾编译器配置。至于网上常见的“microsoft visual C redistributable”之类的问题和竞赛环境没什么关系不需要理会。还有一个小习惯写完代码先自己造几组边界数据测试比如只有一件衣服K1所有衣服含水量都为0K特别大比如100000远大于含水量含水量全相等N1含水量等于1K1这几组数据能帮你快速验证二分上下界有没有写错、check函数有没有逻辑漏洞。我在带队练习时总跟学生说AC的代码不是一次写对的是测出来的。你省了测试的时间就要花更多时间在罚时上。这道P1843奶牛晒衣服如果你能独立把贪心模拟的思路演进到二分答案并且把check函数写得又短又准那GESP五级里的二分答案类题目你基本就过关了。后面再遇到类似题目你会发现核心思想都是同一套猜答案、验可行性、缩范围、输出结果。顺着这个思路去练越练越顺。
