CQOI2010的扑克牌是我给社团学弟讲二分答案时必讲的一道题。每次讲到check函数他都要打断我一次第一次问joker是不是什么都能顶第二次问那为什么不把joker全塞给最缺的那种牌第三次问二分的右边界到底开多大。这三个问题恰好对应这道题的三道思维关卡。题目本身不长n种牌、每种c[i]张、m张joker问最多能组成多少套“n合一”的套牌可它把二分答案的典型气质表现得非常充分直接构造难、判定容易、边界易错。这篇文章就从这三个问题展开把CQOI2010拆开揉碎讲透顺便把整数二分的板子也练扎实。1. 题意的三个坑joker、套牌和“每套最多一张”1.1 原题到底在说什么先完整描述一遍题意。有n种普通牌第i种牌有c[i]张另有m张joker。现在要组“套牌”每套牌必须包含n种普通牌各一张joker可以当作任意一种普通牌来补位但每一套牌里最多只能出现一张joker。问最多能组成多少套。这里最容易被忽略的是最后一条每套最多一张joker。很多人第一眼只记住“joker万能”然后默认joker想用多少用多少结果后面check函数怎么写怎么错。真正读题时建议把这句话圈出来它是正解里那个“need x”条件的来源。数据范围方面n一般不超过50c[i]和m都可能到10^9量级。这意味着两件事一是答案本身可能很大二是任何“模拟拼套”的算法都没戏必须往数学判定上想。1.2 “万能”不等于“无限”可以用组装电脑来类比。CPU、显卡、内存各有库存joker是一块“百变扩展卡”能插到任意一个槽位上但一块卡只能插一个槽一台机器最多插一块。你说你有100块扩展卡可CPU只有3颗那你最多也只能装3台机器因为每台机器的CPU槽位必须被CPU或者扩展卡占用而扩展卡不能同时又当CPU又当显卡又当内存。这个类比很重要。它说明joker不是给某个牌种无限加量而是帮“缺口”补位。判断一组牌能不能凑成x套本质是检查所有缺口加起来joker能不能顶住。一旦建立起“补缺口”的直觉后面check函数的推导就很自然了。1.3 一个推翻直觉的边界例举个反直觉的极端数据n2两种牌各有100张joker有十亿张。直觉反应是“每种普通牌各100那最多100套吧”错。实际上答案能到200套。做法是拿100张joker顶第1种牌的缺另外100张joker顶第2种牌的缺。为什么到201套就不行了算一下组成201套时第1种牌需要201张普通牌只有100张缺101张第2种同样缺101张总缺口是202。但201套最多只能放201张joker所以缺口超过套数上限拼不出来。这个例子告诉我们想靠某一种普通牌的数量直接定上限非常容易算错。老老实实走到判断函数里把所有牌位一起看才算得准。2. 为什么直接贪心会卡住从构造到校验的思维转折2.1 最容易想出的贪心长什么样很多初学者看到这道题第一反应是“补短板”。思路是每轮找到当前数量最少的那种牌用一张joker把它补到和第二少的一样多然后整体抬高。听着很像水桶原理好像也挺有道理但这套方案有个很大的问题你很难证明它是全局最优的。举个例子你决定把第1种牌补到x补到一半发现第2种牌还差一大截joker已经快用完了。这时候你会纠结是不是一开始应该把joker拆给两种牌一起补这种“是不是应该”的判断每补一张joker都要重新做一遍维护成本非常高。更麻烦的是本题的约束是跨套的每套最多一张joker。它不是简单的一维水桶而是一个多维资源分配问题贪心决策很容易顾此失彼。2.2 贪心真正麻烦的地方有人可能会说某些数据下“每轮补最少的牌”看起来也能得到正确答案。对但不代表这策略可靠。一是证明困难你很难找到一个简洁的不变量来说明局部决策总是最优二是即使策略正确复杂度也撑不住。c[i]和m是10^9级别你不可能真的从0开始一轮一轮补到答案。这里我想特别强调一个误区把joker全塞给最缺的那种牌看起来很果断实际上是在忽略“其他牌也在缺”这件事。比如最后剩下的joker够补第1种但第2种也差你才发现之前分配得太冲动了。这类问题适合用总量思维而不是顺序思维。每张joker补到哪个缺口其实不关键关键的是所有缺口的总数是否在两个上限以内。2.3 跳跃从“怎么拼”变成“能不能拼”这道题最有价值的思维切换是从构造问题变成判定问题。不要直接回答“最多几套”而是问“x套可行吗”。“x套可行吗”不需要你真的给出拼法只需要把缺口算清楚。判定问题通常比构造问题简单得多。拼法可能有无数种但缺口总量是确定的。一旦把“怎么拼”的烦恼扔给数学不等式思路就清爽了。二分答案本质就是把这个判定函数套在一个单调的“x可行性”上用对数级别的次数反复问最后逼近那个最大合法值。3. 二分答案的正确姿势先写判断函数再写二分3.1 单调性必须先想明白二分能用的前提是单调性。在这道题里很直观如果x套牌能组成那么x-1套也一定能组成随便扔掉一套剩下的依然合法。反过来如果x-1套都组不成那x套更不可能。所以“可行”这个性质在数轴上是一个前缀区间从0到某个答案都是可行过了答案就全部不可行。我们要找的就是可行前缀的最右端。这是经典的“求最后一个可行位置”的整数二分和“找第一个不可行位置”本质上是一体两面。理解了这个单调性你就不会担心二分会漏掉答案因为可行性永远不会出现“true, false, true”这种震荡。3.2 判断函数怎么一步步推出来现在给定一个具体的x怎么判断x套能否组成按牌种来看。第i种牌如果数量足够即c[i] x那么这x套里第i种的位置不需要joker帮忙如果数量不够即c[i] x那么每套都需要一张第i种牌缺口是x - c[i]这些缺口只能由joker顶替。把所有这样的缺口加起来记作need。到这里很多教程会直接说“need m就可行”但这是不完整的。这道题最妙的地方在于还有第二个条件x套牌总共只有x个joker名额因为每套最多一张joker所以整个方案里能用到的joker总数最多就是x。换句话说need必须同时小于等于m和x。所以判断函数的核心是一句话need m 且 need x。写成数学形式就是 need min(m, x)。3.3 为什么要写成 sum(max(0, x - c[i]))有些同学会问为什么缺口是这么加的而不是直接算 n*x - sum(c)这两者其实等价但前者写起来更直观。注意当c[i] x时多出来的普通牌不能拆给别的牌种用。每套必须包含“第i种”这张牌多的第i种不是万能的它不能变成第j种。这个道理就像食堂窗口排队某个窗口囤了一万份米饭另一个窗口只有一份菜你不能把米饭调过去当菜用。joker才是那个可以跨窗口调配的特殊资源。所以计算缺口时c[i] x的贡献记0只有c[i] x的才产生正缺口。把所有缺口求和就是整套方案对joker的真实需求量。4. check具体实现别漏掉need与x的比较4.1 完整代码和提前剪枝直接给一份完整的C实现工程上很简洁#include bits/stdc.h using namespace std; typedef long long ll; int n; ll m; ll c[55]; bool ok(ll x) { ll need 0; for (int i 1; i n; i) { if (c[i] x) { need x - c[i]; if (need m || need x) return false; } } return true; } int main() { scanf(%d%lld, n, m); ll mx 0; for (int i 1; i n; i) { scanf(%lld, c[i]); mx max(mx, c[i]); } ll l 0, r mx m 1, ans 0; while (l r) { ll mid (l r) 1; if (ok(mid)) { ans mid; l mid 1; } else { r mid - 1; } } printf(%lld\n, ans); return 0; }细节上有两点值得说明。第一循环里的剪枝可以放心写因为need是只增不减的一旦超过m或x后面继续累加只会更糟提前返回不会出错。第二最后返回true时说明所有缺口之和既没超过joker总数也没超过套数上限判定成立。4.2 当m很大时只写needm会翻车这是CQOI2010最阴的一个点我亲眼见过一堆人在正式数据上死在这里。构造一组数据n3c [2, 2, 100]m 100000。尝试组5套第1种牌缺3张第2种牌缺3张第3种不缺总缺口need6。如果check只写need m6 100000成立你会认为5套可行。但5套牌里最多只能有5张joker缺口需求是6根本塞不下。所以正确答案连5套都不到稍微再算一下会发现答案是4套。这就是“每套最多一张joker”这条约束在作怪。joker总数够不代表每个套里能塞进这么多张joker套数x本身就是第二道天花板。4.3 joker很多但套牌位置不够的情况再回到前面的极端用例n2两种牌各100张m10^9。在x201时两种牌各缺101张need202m充足但x201不够判定失败。此时瓶颈不是joker库存而是“x套一共只能容纳x张joker”这个结构限制。这类数据最容易测出check是否漏条件。训练时建议自己手写这一组极端用例把不等式烧进脑子里。只要看到问题里出现“每套最多一个万能牌”之类的限制就可以条件反射地警惕第二道天花板。5. 整数二分三种常用写法和上界选择的取舍5.1 闭区间加ans记录的写法我最推荐初学者用的是闭区间加ans记录也就是上面代码里那种写法。它的优点是直观、不容易写错、不会死循环。ll l 0, r mx m 1, ans 0; while (l r) { ll mid (l r) 1; if (ok(mid)) { ans mid; l mid 1; } else { r mid - 1; } } printf(%lld\n, ans);核心逻辑是mid可行就把答案记录到ans然后往更大的区间找mid不可行就收缩右边界。循环结束时l超过r而ans里存的是最后一个可行的mid也就是最大套数。5.2 左闭右开的写法另一种常见写法是保持左闭右开区间[0, r)其中l一定是可行值r一定是不可行值不断把边界向中间推。ll l 0, r mx m 1; while (l 1 r) { ll mid (l r) 1; if (ok(mid)) l mid; else r mid; } printf(%lld\n, l);循环结束时l是最后一个可行值。这种写法要求你初始化时保证l可行、r不可行。这道题里l0一定可行rmxm1一定不可行所以可以直接用。注意循环条件是l 1 r别写成l r否则相邻时会卡死。5.3 上界的选取别总想着0x3f3f3f3f二分上界的选取是个容易踩的坑。很多人习惯性写0x3f3f3f3f但这个常量的十进制约是10.6亿而这题答案可能到20亿甚至更大直接会漏掉正确解。我更喜欢这几种上界。上界写法是否安全说明0x3f3f3f3f不安全只有约10.6亿答案可能超过mx m 1安全有一种普通牌最多mx张若总套数x超过mxm仅这一种牌的缺口就超过m张joker(sum(c) m) / n 1安全且更紧n*x个牌位最多由sum(c)m张牌提供x不可能超过这个值为什么mx m 1一定不可行因为取出任何一种普通牌设它最多有mx张。若想组成x套这种牌需要x张普通库存最多mx张剩下的x - mx张必须由joker顶替。joker总数是m所以x - mx m必须成立即x mx m。因此把右边界取成mx m 1它是确定不可行的。同时别忘了全程用long long。n*x可以达到50乘以2e9量级int根本装不下。mid取(l r) 1时l和r也可能相加超过int范围必须用64位整数。5.4 防止死循环的细节闭区间写法不会死循环因为每次循环要么l增大到mid1要么r减小到mid-1区间严格缩小。左闭右开写法要记住l 1 r这个条件其实就是为了保证mid不等于l否则会原地打转。初学阶段建议只练一种板子练到肌肉记忆别在板子上花太多精力。二分真正难的是check函数板和边界只是基本功。6. 复杂度分析、同类题识别与我的三点实战心得6.1 复杂度二分范围大约是mx m量级在2e9左右二分次数约31次n最多50每次check是O(n)。总复杂度O(n log(mx m))实际也就一千多次操作轻松通过。这个复杂度是这道题设计得很好的地方数据范围故意给到10^9逼你放弃遍历但n很小允许你在O(n)的判定函数上反复跑。6.2 怎么识别“二分答案”的信号刷题时看到这类特征可以第一时间往二分答案上想问题问的是“最大可行值”或“最小可行值”答案的可行性具有单调性直接构造或模拟太慢但判断“给定x是否可行”很容易。本题三样全占问最大套数可行是前缀判定只要算缺口和。同类题还包括很多“最大化最小值”“最小化最大值”的题判断函数往往是一段贪心扫描。这类题的核心套路是一样的先把判断函数写好再套二分板子而不是先抄板子再补判断函数。6.3 我的三点实战心得第一写check之前先把不等式列在草稿纸上。我见过太多人先把二分模板抄出来然后对着空白的ok函数发呆。正确顺序是先在纸上推出need m need x再动手写代码。这题的所有难度都藏在推导里不把不等式想清楚代码怎么写都是错的。第二写完一定要用极端数据自测。我喜欢测三组一组是joker很多但每套限制卡死比如n2、c[100,100]、m10^9一组是joker很少但有牌缺口很大还有一组是n1的退化情况。这三组过了代码基本就稳了。很多同学的代码样例能过但极限数据直接挂就是因为没提前自测第二道天花板。第三板子固定成闭区间加ans记录。整数二分最容易写的其实不是边界而是循环结束后的答案确定。闭区间写法里ans始终记录最后一个可行值即使现场紧张也不会搞混。左闭右开虽然也很标准但初学阶段需要维护“l可行、r不可行”的语义多一层心智负担。我后来长期刷题一直用闭区间加ans省下来的精力都留给判断函数本身了。