最近在翻 Codeforces 题单的时候又把 CF1267J Just Arrange the Icons 翻了出来。这道题表面是“给图标排屏幕”实际上是一道非常典型的计数 枚举思维题代码不长但把约束条件转换成数学表示那一步很值得玩味。我最初做的时候想直接贪心结果样例都过不了后来老老实实把题意剥开才发现核心就是一个“整除 余数”的判定。这篇文章就围绕 CF1267J 的完整思路、枚举剪枝和代码实现展开适合正在刷 Codeforces div2/div1 构造题、或者备战区域赛的选手参考看完可以直接拿去提交。1. CF1267J 题意还原别被“图标”这个壳骗了1.1 原始场景里到底发生了什么Codeforces 上的题目喜欢套一层生活化的壳CF1267J 也不例外。题目说有 n 个应用图标每个图标有一个颜色相同颜色的图标属于同一类。现在要把这些图标放进若干个屏幕里每个屏幕的容量都是一个固定的正整数 S而且屏幕里只能放同一种颜色的图标不能混色。最关键的限制是每个屏幕要么装满 S 个图标要么只装 S-1 个图标不允许出现空很多位置的情况。目标是在所有可行方案里选出屏幕总数最小的一种输出这个最小屏幕数。我最早读题的时候把“要么装满要么少一个”这个细节看漏了以为只要每个屏幕同色、容量固定就行。那问题就退化成“每种颜色分一屏或者尽量塞满”答案基本等于颜色种类数完全体现不出这道题的思维量。这个“满屏或差一屏”的约束才是整道题的题眼。1.2 为什么不是简单的 ceil(cnt / S)如果只看“每个屏幕最多放 S 个同色图标”那对于每种出现次数为 cnt 的颜色所需屏幕数是 ceil(cnt / S)总屏幕数就是所有颜色求和。由于 ceil(cnt / S) 随 S 增大而单调不增直接把 S 取到无穷大答案是颜色种数 m。但 CF1267J 显然不可能让你输出 m所以题目一定比这个复杂。现在把“差一屏”加进来问题就变成对每种颜色它拥有的 cnt 个图标必须能被拆成若干个“满屏 S”和若干个“差一屏 S-1”的和。一个颜色可以同时有多个满屏和多个差一屏但所有屏幕的屏幕数加起来要尽可能少。于是问题变成了一个纯数学问题对于每个候选 S判断每个 cnt 能不能写成 aS b(S-1) 的形式其中 a 和 b 都是非负整数如果能这组方案所需的屏幕数是多少。这一步转化是整个 CF1267J 的关键。不把这个模型建出来后面所有优化都无从谈起。1.3 输入规模与统计方式CF1267J 的 n 上限我记得是 2e5 左右颜色编号可以很大。所以第一步一定是压缩统计把所有颜色出现的次数统计成一个数组 cnt。统计方式我个人推荐 sort 扫描而不是 unordered_map。原因很实在Codeforces 的比赛环境里unordered_map 被卡已经不是新闻了尤其是大量插入、哈希碰撞严重的时候明明 O(n) 的复杂度能跑完却因为哈希退化变成 O(n^2) 然后 TLE。sort 的复杂度是 O(n log n)但胜在稳几乎不会出幺蛾子。而且排序之后去重计数非常自然代码也短。vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); vectorint cnt; for (int i 0; i n; ) { int j i; while (j n a[j] a[i]) j; cnt.push_back(j - i); i j; }这样 cnt 数组的长度就是颜色种数 m每个元素是当前颜色出现的次数。接下来所有讨论都建立在这个 cnt 数组上。2. 核心判定满屏与差一屏的数学等价条件2.1 把“是否能拆”变成整除与余数问题假设当前枚举的屏幕容量是 S某一种颜色出现了 cnt 次。我们要判断是否存在非负整数 a 和 b使得cnt a * S b * (S - 1)其中 a 是满屏数量b 是差一屏数量。这个式子本身不难难点在于如何高效判断。最朴素的做法是枚举 a 或 b但那样单次判定就是 O(cnt / S)整体会超时。好在这个式子可以被“整除 余数”压缩成 O(1) 判断。先做一次整数除法q cnt / S r cnt % S也就是 cnt q * S r其中 0 r S。如果 r 0说明 cnt 恰好能分成 q 个满屏不需要差一屏屏幕数就是 q。如果 r 0说明只靠满屏装不完还剩 r 个图标。这 r 个图标必须放到某个差一屏里或者通过调整一些满屏为差一屏来消化。这时候需要额外判断。2.2 r 0 时的一行判定条件当 r 0 时存在可行拆分的充要条件是q r S - 1这个式子看起来很突兀我推导一下你就明白了。如果用到差一屏那么总屏幕数 t 至少是 q 1因为 q 个满屏只能装 qS 个装不下 cnt 个。假设总屏幕数为 t所有 t 个屏幕满容量一共能装 tS 个图标实际装了 cnt 个那么“空位”数量就是tS - cnt tS - (q*S r) (t - q)*S - r如果 t q 1空位数就是 S - r。差一屏的定义是每个屏幕比满屏少 1 个图标所以 S - r 个空位需要分布在 S - r 个差一屏上。要保证差一屏数量不超过总屏幕数必须满足S - r t代 t q 1 进去就是 S - r q 1移项得到 q r S - 1。所以判断条件就是这一行。实际写代码时我习惯先特判 r 0然后统一判断 q r S - 1。2.3 用一个生活类比加深理解把 S 想象成标准停车位的长度S-1 是短车位长度。现在有一排车总长度是 cnt你要用标准车位和短车位把车全停进去而且短车位只是短了一点不能短太多。q 是“如果全用标准车位需要多少个完整车位”r 是最后剩下的一截。如果 r 为 0整整齐齐完美。如果 r 不为 0就需要一个短车位来收尾。但短车位的长度是 S-1也就是说它比标准车位少 1整个方案总共能产生多少个“少 1”的余量取决于你用了多少个短车位。q r S - 1 的本质就是告诉你剩下的这段 r 能否被足够多的短车位“消化”掉而不是出现一个根本塞不下的碎片。我第一次看到这个式子的时候也觉得像是魔法后来手动枚举了几个例子才发现它其实就是在数空位够不够分。3. 枚举 S 的上界与复杂度证明3.1 为什么 S 只需要枚举到 minc 1确定了单个 cnt 的判定方法之后下一步就是枚举 S。S 理论上可以很大但题目里有一个天然上界所有颜色中出现次数最少的那个值记为 minc。如果 S minc 1对于出现次数为 minc 的那种颜色一定有 q 0r minc。此时判断条件 q r S - 1 就变成了minc S - 1但 S minc 1 意味着 S - 1 minc条件必然不成立。也就是说只要 S 超过 minc 1数量最少的那个颜色就一定无法被拆分整个 S 直接作废。所以枚举范围可以放心地限制在 [2, minc 1]。这是这道题最重要的剪枝也是我一开始没想通的地方。我一直把 S 枚举到最大出现次数结果 TLE后来看到题解才意识到答案根本不会来自更大的 S。3.2 总复杂度为什么是 O(n) 级别这个枚举范围看起来只是缩小了上界但配合 cnt 数组的性质复杂度非常可观。设颜色种数为 mminc 是出现次数最小值。因为每个 cnt[i] minc所以所有颜色的出现次数总和 n 一定满足n sum(cnt[i]) m * minc也就是说m n / minc而枚举的 S 数量是 minc 个左右从 2 到 minc 1。如果对每个 S 都遍历所有 m 种颜色总检查次数大约为minc * m n这是一个非常漂亮的结论不管数据怎么构造枚举 判定的总工作量被 n 限制住整体是 O(n) 的。再加上排序的 O(n log n)整个程序在 n 2e5 的规模下可以轻松跑过。当时看到这个复杂度证明的时候我确实有点惊讶。通常枚举一个参数再检查所有颜色会是 O(n^2)但这里因为“出现次数最小值”同时限制了枚举上界和颜色数量两个变量互相制约反而把复杂度压下来了。3.3 枚举过程的剪枝实现虽然复杂度已经是 O(n)实际操作中还是可以做一点小优化减少常数。比如在枚举某个 S 时只要发现任何一种颜色不满足条件直接 break 掉不再检查后面的颜色。另外可以用一个当前最优值 ans 做下界剪枝如果当前已经累加的屏幕数 cur 已经大于等于 ans也可以提前退出。这两个剪枝在本题不是必须的但写上去之后代码在面对多组数据时会明显更快。特别是 Codeforces 的题目经常有多组测试能省一点是一点。long long ans n; // 屏幕数不可能超过 n用它做初始上界 for (int s 2; s minc 1; s) { long long cur 0; bool ok true; for (int c : cnt) { int q c / s; int r c % s; if (r 0) { cur q; } else if (q r s - 1) { cur q 1; } else { ok false; break; } if (cur ans) break; } if (ok) ans min(ans, cur); }这里 ans 初始化为 n因为每个屏幕至少装 S-1 1 个图标所以屏幕数不可能超过图标总数 n。用 n 做初始上界完全够用不需要设成很大的数。4. 完整代码与常见坑点4.1 可直接提交的 C17 代码把上面的逻辑拼起来完整的 CF1267J 可提交代码是这样的#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); vectorint cnt; for (int i 0; i n; ) { int j i; while (j n a[j] a[i]) j; cnt.push_back(j - i); i j; } int m (int)cnt.size(); int minc *min_element(cnt.begin(), cnt.end()); long long ans n; for (int s 2; s minc 1; s) { long long cur 0; bool ok true; for (int c : cnt) { int q c / s; int r c % s; if (r 0) { cur q; } else if (q r s - 1) { cur q 1; } else { ok false; break; } if (cur ans) break; } if (ok) ans min(ans, cur); } cout ans \n; } return 0; }这里唯一需要注意的类型问题是 cur 和 ans 用 long long。n 最大 2e5 左右时 int 也够但多组数据累计下来习惯用 long long 更保险。4.2 提交时最容易踩的几个坑第一个坑是直接用 unordered_map 统计颜色然后遍历 unordered_map。我知道很多人喜欢这样写因为代码短。但就像前面说的CF 的 hack 数据经常会针对 unordered_map 制造大量哈希碰撞导致程序被卡到超时。用 sort 排序统计看着笨实际最稳。第二个坑是判定的边界写错。我见过有人把 r 0 的情况也拿去做 q r s - 1 的判断这样在 cnt 恰好是 S 的倍数时可能多算一屏甚至误判不可行。r 0 一定要单独处理直接加 q。第三个坑是 S 的枚举上界。有些题解写的是枚举到 minc 1但如果你把上界写成 maxc提交也不会 WA只是慢一些极端数据下可能 TLE。因为 minc * m n 这个漂亮结论就失效了最坏会变成 O(maxc * m)当出现次数最大值很大、颜色种类也很多时直接爆炸。第四个坑是多组数据的变量重置。cnt、minc、ans 每一轮都要重新计算别把上一轮的残留数据带到下一组。4.3 几个极端样例手算验证为了确保代码没有理解偏差我习惯在本地跑几个极端样例。第一种情况所有颜色都只出现一次比如 n 5五个颜色各不相同。cnt 数组是 [1,1,1,1,1]minc 1。S 只能枚举到 2。对每个 c 1q 0r 1q r 1 1可行cur 1。五个颜色加起来 ans 5。也就是说每个颜色单独占一个屏幕屏幕容量是 2 但只放 1 个符合题意。第二种情况只有一种颜色出现次数 n 6。cnt [6]minc 6。S 枚举 2 到 7。S 2 时q 3r 0cur 3可行。S 3 时q 2r 0cur 2可行。S 4 时q 1r 2q r 3 3cur 2可行。S 5 时q 1r 1q r 2 4不可行。答案最终是 2。也就是说 6 个同色图标可以用两个屏幕每个屏幕 3 个或者一个满屏 4 个加一个差一屏 2 个不对S4 时差一屏是 3装 2 个还是差 2 个让我重新检查一下S4时cnt6q1r2条件 qr3 3 成立按公式 tq12空位 tS - cnt 8-62分布在2个差一屏上但这里如果只有一个差一屏空位2代表差1屏放2个其实 S-13放2个是差2个不行。但公式说空位数 S-r 2需要分布在 t2 个屏幕上意味着两个屏幕都是差一屏每个差一屏少1个总共少2个两个屏幕每个装3个总装6个。但题目要求每个屏幕要么满屏要么差一屏两个都差一屏每个装 S-13正好装6。等等这样确实是两个屏幕各装3个即 b2, a0cnt 04 2*3 6。没问题。S5时cnt6q1r1若tq12空位10-64需要分布在4个差一屏但只有2个屏幕不可能。所以不可行。很好公式和直觉一致。这些极端样例跑下来代码的判定逻辑是自洽的。5. 经验总结这类 Codeforces 思维题的通用套路5.1 从“能不能”到“怎么最少”的思考顺序CF1267J 这类题的特点是表面是构造或模拟实际上第一步永远是判断可行性第二步才是在可行方案里找最优。很多人上来就想通过贪心确定屏幕数量方向就错了。正确的顺序是先明确一个参数 S然后对每个颜色做可行性判定再计算屏幕数。判定可行性的工具是数学化把约束写成等式或不等式再用整除、余数、不等式这些基础手段 O(1) 判断。这种“枚举一个参数 判定一个性质”的模式在 CF 构造题里出现频率非常高。如果你刷题时遇到类似“选出某个参数使得每种东西都能被某种规则装下”的题目第一反应应该是能不能把规则转成数学条件能不能用枚举参数 O(1) 判定来做这两个问题想清楚题目就解决一半了。5.2 复杂度上界被“最小出现次数”卡住这个题的复杂度分析非常有启发性。它告诉我们枚举一个参数未必会导致 O(n^2) 的复杂度只要这个参数和其他变量之间存在制约关系。CF1267J 里minc 同时限制了枚举上界和颜色数量于是 minc * m n总复杂度被压到线性。这种“互相制约”的思路在 Codeforces 的出题里经常出现尤其是 Div2 的 D 题和 Div1 的 B 题。当你觉得一个暴力枚举方案看起来要超时先别急着放弃分析一下枚举范围和检查范围之间有没有乘积关系也许结论是可行的。5.3 推荐配套练习同类构造与枚举题如果你想把这种“题意转数学 枚举判定”的思路练熟我建议除了 CF1267J 之外再去看几道 Codeforces 上的同类型题目。最近 CF 上就有一些这类题热度很高比如 D 题的 XOR of 3、Polycarp and Snakes都是那种“先抽象条件再通过数学变换找到突破口”的构造/枚举题。做这类题的时候别急着看题解先自己动手推。推不出来就看题解的前半部分看懂“怎么把题面转成数学表达”那一步然后再自己完成后续。这种“半提示式刷题”对训练建模能力特别有效。我个人的体会是CF1267J 的价值不在代码本身而在那个从“满屏/差一屏”到“q r S - 1”的思维跳跃。想通这一下以后遇到类似的“屏幕容量限制”问题你就能少走很多弯路。