CF1399C这道题在Codeforces Round #1399 Div. 2 里排在第三题，说难不难，但掉坑的人真不少。题目用一句大白话概括就是：给你一堆选手的体重，让你两两配对去划船，要求每组两个人的体重之和必须完全相等，问最多能凑出几组。很多人读完第一反应是贪心，想直接从体重最重的开始配，结果样例都过不稳。我当初也是从错误思路里爬出来的，后来才意识到这道题真正考的不是配对技巧，而是“枚举目标”这个朴素但极其有效的思路。
如果你是刚开始刷CF的选手，大概在1200到1600分这个区间，那这道题是很合适的练手素材。它不涉及高深的算法，只要你会用数组统计、会写循环、能理解双指针的基本逻辑，就能在半小时内拿下一道Div. 2 C题。这篇文章我会把我的完整思考过程、两套可行解法、以及我实际调试中踩过的坑都讲清楚，代码我会给到可以直接抄的版本，但更重要的是把“为什么这么想”说明白。
1. 先把题目吃透：它在考什么
1.1 题目背景与我的第一反应
先说题目本身。CF1399C的正式名字叫Boats Competition，意思是“划船比赛”。输入一个数组w，w[i]表示第i个选手的体重，你要把人分成若干组，每组正好两个人，而且每一组两个人的体重和要等于同一个数值S。注意这个S是固定的，所有能成功配对的队伍必须满足a+b=S。没被分到组的人可以剩下，这没问题，我们的目标只是让配出来的组数尽可能多。
我第一次看到这个题，脑子里跳出来的想法是：先把体重排序，然后用最大和最小去配。比如体重是[1, 2, 3, 4, 5]，S如果等于6，那可以是1+5、2+4，剩下3自己闲着。但问题在于S不是一个已知输入，它是隐含在最优配法里的。你根本不知道S该取多少，那“最大配最小”这个贪心策略就失去了方向。
更坑的是如果你凭感觉取S，比如取数组最大值加次大值，那么在很多情况下并不是最优解。举个例子，体重是[1, 1, 1, 2, 2, 2]，如果你取S=4，那么只能配出2+2这一对，剩下四个1没法配；但如果你取S=3，就能配出三组1+2。这说明S的选择直接决定答案，而你没法一眼看出来该选哪个S。
1.2 核心考点拆解：从暴力到枚举
这道题真正想让你掌握的，是“枚举可能解”的思维。因为体重的数据范围很小，原题里n最大只有50，每个wi也不超过n。这意味着两个人体重和S的范围极其有限，从最小值2一直到最大值2n，总共也就一百来个候选值。既然候选的S这么少，那最靠谱的思路就是把每个S都试一遍，统计每个S能配出几组，取最大值，完事。
这就是枚举法的精髓：当你要在某个未知参数上做最优决策，而且这个参数的可能取值非常有限时，枚举比贪心靠谱得多。你不需要去猜S是多少，你只需要把每个可能的S都当一次“标准答案”去检验，看哪个S返回的配对数最多。
这里就引出了第二个考点：给你一个固定的S，你如何高效地算出能配成几组？最容易想的是二重循环，遍历所有i和j，检查w[i]+w[j]==S且两人未被使用。但这么写复杂度是O(n^2)乘上S的枚举量O(n)，在n=50时能过，但代码容易写乱，还要维护“已使用”标记。更漂亮的方案是用计数数组统计每个体重出现多少次，然后一次性配对。
核心思路是这样的：如果一对选手的体重是a和b，且a+b=S，那么只要体重a的人数有na个，体重b的人数有nb个，你能配出的对数就是min(na, nb)。这个结论是整道题最关键的地方，它把“配对”这个动作简化成了一次简单的数学计算，不需要关心具体是哪个选手跟哪个选手，只看数量就够了。
2. 为什么枚举总重量这条路能走通
2.1 关键性质：所有的配对必须拥有同一个S
继续往深挖一层。题目要求所有配对的体重和都是同一个S，这意味着什么？意味着如果你已经确定了S的值，那么每一对（a, b）都必须满足b=S-a。也就是说，体重a只能和体重S-a配对，没有任何其他选择。这个性质让问题变得非常“死板”，而这恰恰是好事。
死板意味着可计算。你不需要考虑组合爆炸，因为每个体重都只有唯一一个“搭档体重”。这就好像开舞会，每个人都只允许找一个特定身高的人跳舞，那么能组成多少对就完全由人数分布决定了。在算法里，我们只需要把a从1扫到n（体重范围的上限），然后看a和S-a这两个体重分别有多少人，取较小值累加。
但这里有个容易翻车的点：如果你直接扫a从1到n，那么当你扫到a时，其实已经把配对（a, S-a）算了一遍；当你继续扫到S-a时，又会把同一个配对再算一遍。如果你不处理，结果会翻倍，答案直接错掉。解决办法有两种：第一，只让a小于S-a的时候才计数，等于的情况单独处理；第二，用一个标记数组记录已经处理过的体重。我推荐第一种，简单直接，不容易出状态残留的问题。
这里还要注意a等于S-a的特殊情况。当a的“搭档”就是它自己，也就是2a=S时，能配出的对数不是min(cnt[a], cnt[a])，而是cnt[a]整除2。因为体重为a的选手只能内部两两配对。举个例子，S=6，体重为3的选手有5个人，那你最多只能配出2组，剩下1个人闲着。用整除2就能正确算出这个数。
2.2 基于计数数组的配对计算法
基于上面的分析，对于一个给定的S，计算最优配对数的伪代码其实只有几行：
- 初始化ansS = 0
- 让a从1遍历到n（体重上限）
- 如果a > S - a，直接跳过，避免重复
- 如果S - a 超出体重范围，也跳过
- 如果a == S - a：ansS += cnt[a] / 2
- 否则：ansS += min(cnt[a], cnt[S-a])
注意我前面强调的体重范围。在实际代码里，体重上限不一定是n，但因为我只关心w[i]的取值范围，所以可以直接开一个大小合适的计数数组。假设体重最大是maxW，那S的范围就是从2到2*maxW。不过原题既然保证了wi <= n，直接按n来开数组最省事，从2枚举到2n即可。
这个计算方式为什么是O(n)的？因为对于每个S，你只扫描了一遍a从1到n，每次做常数时间的判断和加法。外层再套一层S从2到2n的枚举，总复杂度是O(n^2)。对于n=50来说，这几乎是瞬间出结果。就算n放大到5000，O(n^2)也就是2500万次操作，在很多语言里依然可以接受。
2.3 双指针判定法的原理与适用场景
除了计数法，很多人的题解还会提到排序+双指针。原理是先把体重数组排序，然后对于每个S，用两个指针l和r分别指向数组两端。如果w[l]+w[r]正好等于S，就配成一组，l加一、r减一；如果和小于S，说明需要更大一些的数来配对，l加一；如果和大于S，说明需要更小的数，r减一。用一个布尔数组记录哪些选手已经被用掉，或者直接在原数组上“拿走”元素。
这套方法在很多“两数之和等于target”的题里都很常用。它的复杂度是O(n)扫描一次数组，配合外层S枚举后是O(n^2)。在本题里它也能过，而且思路非常直观，适合刚学双指针的人练习。但它有两个麻烦：第一，每个S都要重新在排序数组上跑一遍双指针，如果你在原数组上做了标记，下一次S还要重置所有标记，处理不好很容易残留状态；第二，双指针的循环里还得处理重复体重，因为排序后相同的数会连在一起，配对时可能一个数被重复计算。这两个坑导致它比计数法更容易写错。
那什么时候必须用双指针而不是计数法？答案是体重范围很大的时候。比如体重可以到10^9，那你没法开10^9大小的计数数组，只能排序后双指针。不过那种情况下枚举S从2到2n也失效了，问题性质已经改变，通常得换思路。所以在CF1399C这道题的数据范围下，计数法是最优选，双指针适合拿来当练习，不适合当主推方案。
3. 代码实现与参数细节
3.1 计数法代码：我的主推写法
直接给代码。我用C++写，因为CF上C++是最常见的提交语言，但你完全可以用Python或Java对照着翻译。
#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; vector<int> cnt(n + 1, 0); for (int i = 0; i < n; i++) { int w; cin >> w; cnt[w]++; } int best = 0; for (int s = 2; s <= 2 * n; s++) { int cur = 0; for (int a = 1; a < s && a <= n; a++) { int b = s - a; if (b < 1 || b > n) continue; if (a > b) continue; // 避免重复计数 if (a == b) { cur += cnt[a] / 2; } else { cur += min(cnt[a], cnt[b]); } } best = max(best, cur); } cout << best << '\n'; } return 0; }注意我在内层循环里写的是a < s && a <= n，这是两个条件。为什么a要小于s？因为如果a >= s，那b = s - a就小于等于0了，不可能是合法体重。同时a本身不能超过n，因为体重最大就是n。b那边同样做了越界检查。这些边界条件看起来不起眼，但少了任何一个都可能让数组访问越界，或者把非法情况算进答案。
再强调一下，为什么内层循环用if (a > b) continue而不是用a <= s/2作为循环终止条件？两种写法本质等价，但if (a > b) continue更清晰，因为a和b的关系一眼就能看出来。当然你也可以写成for (int a = 1; 2 * a <= s; a++)，这样连判断都省了。我个人的习惯是2*a <= s，它确保我们只处理a小于等于b的情况，但要注意当a等于b时，2*a等于s，此时整除2的逻辑要写对。
3.2 双指针版本代码与对比
既然前面提到了双指针，我就把双指针的参考实现也贴出来，方便你对比调试。我这里选择每次都重新复制一个临时数组，防止上一个S的配对结果污染下一次循环。
#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; vector<int> w(n); for (int i = 0; i < n; i++) cin >> w[i]; sort(w.begin(), w.end()); int best = 0; for (int s = 2; s <= 2 * n; s++) { vector<int> tmp = w; // 复制一份，避免污染 int l = 0, r = n - 1; int cur = 0; while (l < r) { int sum = tmp[l] + tmp[r]; if (sum == s) { cur++; l++; r--; } else if (sum < s) { l++; } else { r--; } } best = max(best, cur); } cout << best << '\n'; } return 0; }这个版本在逻辑上很干净，因为临时数组tmp在每个S下都是全新的，不存在标记重置问题。但代价是多了一次O(n)的数组复制，外层S有2n个，复制成本就是O(n^2)，在n=50时无伤大雅。如果你想优化，可以只维护一个visit数组来标记某个下标是否已被使用，但那样循环退出条件和指针移动都要多加判断，代码反而更难读。我在实际写的时候更倾向于每次重新复制，简单明了，反正数据量小。
对比这两个版本，我的体会是：计数法更适合作为标准答案，因为它代码短、逻辑直白、不容易产生隐藏bug；双指针更适合作为理解“双指针如何配对”的训练题。如果你在练习阶段，两个都写一遍很有价值；如果是在比赛时图稳，计数法是第一选择。
3.3 几个容易写错的细节
第一，体重范围不要想当然。有人看题目说n最大50，就觉得体重最多也是50。这没问题，但如果你在代码里写死了计数数组大小是51，而体重输入中存在等于50的值，cnt[50]是合法的；可如果你循环枚举S时写到2n，也就是100，那么内层a最多到50，b可能到99，你访问cnt[b]之前必须先判断b <= n，否则数组越界。很多人的Runtime Error就是这么来的。
第二，内层循环里a的终止条件。如果你写for (int a = 1; a <= 2 * n; a++)，不判断a和b的大小关系，那么当a=2, b=3和当a=3, b=2时，你会把同一对选手算两遍。我见过有人在这个问题上调了半天，就是没搞清楚为什么结果总比答案大一倍。解决办法就是我前面说的让a只跑到2*a <= s，或者在循环体内加if (a > b) continue。
第三，不要忘记处理a == b。有些选手体重是s的一半时，他们只能内部配对，个数是cnt[a]/2。如果你用min(cnt[a], cnt[a])，结果还是cnt[a]本身，等于把一个体重为a的选手同时用在了两支队伍里，答案就虚高了。这类对“单人重复使用”的错误在计数法里极其隐蔽，因为你看到的数字依然合理，但实际上是错的。
4. 常见问题与调试实录
4.1 遇到重复体重时配对计数错误
先说一个真实场景：我当时拿样例去跑，样例里有不少重复体重，比如[1, 2, 2, 3, 4, 5]这类。用计数法时，每个体重的计数是明确的，理论上不会出错。但问题出在我第一次写的版本里，我用的是cur += max(cnt[a], cnt[b])而不是min(cnt[a], cnt[b])，结果答案偏大。
为什么是min而不是max？你想想，如果体重a有3个人，体重b有5个人，你只能配出3对，因为a方人数不够。剩下的2个b方选手就闲着。用max就会得到5，这意味着你把不存在的3个a选手变成了5个，显然是错的。这个细节我在调试时是构造了一个只有一组能配全的例子才发现的：cnt[1]=1, cnt[5]=5，S=6，正确答案是1，但max版本算出5。这种单测一造出来，问题立刻暴露。
4.2 边界值导致数组越界的处理
还有一个典型报错是数组越界。比如S枚举到2n，内层a从1开始，如果某个a值比较大，比如a = n，而S也很大比如2n，那b = 2n - n = n，这个值恰好等于n，是合法的。但如果a = n而S = 2n - 1，则b = n - 1，也合法。什么时候会不合法呢？当a > S时，b是负数。所以循环时要保证a < S。这个条件我建议直接写在for语句里，别放在循环体内判断，否则一旦循环变量越界，你先访问了cnt[b]再判断就晚了。
还有体重输入时可能出现0吗？题目里体重都是正整数，所以不用考虑。但如果你把计数数组从0开始，并且在循环里让a从0扫，那你可能会把体重为0的选手算进去，这显然不符合题意。我的习惯是让体重下标从1开始，这样数组空间多开一个，逻辑上也更贴合“选手体重至少是1”的设定。
4.3 样例过了但提交WA的排查思路
这道题很诡异的一点是，样例往往都过得很顺利，但一提交就WA。我当时第一次提交WA在Test 3，然后就开始瞎调。后来我静下来自己生成了一组随机数据，然后写了一个O(n^3)的暴力程序作为对拍器，才找到了问题所在。原来我在枚举S时，上限写成了max element * 2，但题目中最大体重不一定等于n，比如体重列表里最大的是47，而n=50，那么存在一种合法配对需要S=50+50=100的情况吗？不可能，因为最大体重只有47，两两之和最多94。所以用maxW*2作为上限其实是安全的，甚至比2n更紧。
问题出在我的内层循环只遍历到maxW，而不是n。如果体重范围小于n，那你可能漏掉某些候选体重为0的情况，但这不影响结果。真正让我WA的是另一个问题：我用了cur += cnt[a]而不是cur += cnt[a] / 2来处理a==b的场景。你以为匹配得很顺利，实际上每个体重为a的人都配了两支队伍，答案虚高。后来我把这个case写进测试集才发现。
这里分享一个通用的排查思路：如果你觉得自己的算法逻辑正确但WA，不要光盯着题目样例，一定要生成几组随机数据，再写一个绝对正确的暴力程序，两者结果对比。我日常刷CF时经常用Python写暴力对拍器，因为写起来快，虽然跑得慢，但数据规模小的时候就无所谓了。
4.4 复杂度分析与进一步扩展
最后聊聊复杂度。我写的计数法，外层枚举S从2到2n，内层遍历a从1到n，总共大约2n * n = 2n^2次操作。n=50时这完全没压力，甚至n=5000也能轻松跑完。双指针版本多了一次数组排序O(n log n)和每次S下的O(n)扫描，总体O(n^2 + n log n)，也完全可以接受。
如果哪天你遇到一个变体题，n变成了10^5，体重值依然很小，但S的取值范围依然最多2n，那么计数法依然成立，只是不能在外层枚举所有S了，因为2*10^5 * 10^5是10^10，超时。这时候你要反过来观察：既然每个S都能O(n)算，但你只需要找最大值，有没有办法剪枝？答案是可以用哈希或者前缀和优化，但这已经超出CF1399C的范围了。如果你在做题时遇到类似的加强版，我建议你先把计数法吃透，因为几乎所有优化思路都是基于它演化出来的。
还有一点，注意CF是多组测试，每组n加起来可能达到某个上限，所以代码里记得每个测试用例都要重新初始化cnt数组，千万不要把上一组的计数残留下来。用vector初始化一行代码搞定，也就是vector<int> cnt(n + 1, 0);。我见过有人图省事用全局数组，但忘记memset，导致样例第二组数据开始结果全飘。这类问题不是思路问题，而是基本功问题，但也同样致命。
5. 这样一类题，怎么练才算真会
说实话，CF1399C这种题并不难，但它覆盖了几个非常关键的解题习惯，值得你反复品味。第一是“枚举未知参数”的思维，很多时候你不知道最优解里的某个关键值是多少，但你能确定它的取值范围很小，那枚举就是最稳妥的解法。第二是“用计数代替配对”的抽象能力，把具体选手的配对问题转换成数量之间的min运算，这比维护used数组清爽太多了。第三是“小心边界与对称性”的意识，凡是涉及两两组合的题，重复计数和自配对问题几乎必然出现，能提前注意到就能省下大量调试时间。
我自己的训练建议是：拿到一道题，先别急着写代码，花五分钟想一想这个问题的答案落在哪个参数空间里。如果是体重和S，那S最多有多少种可能？如果可能很少，枚举就是正路。然后想清楚判定函数怎么写最不容易错，是计数法还是双指针。最后再动手写代码。这三步走下来，你会发现CF的很多Div. 2 C题都遵循类似的套路。
做这道题的时候，我还有一个额外的体会：对拍器真的是CF选手的好朋友。你用暴力法作为基准，去验证优化后的算法，几分钟就能找到隐藏的边界错误。那次我用对拍器找到a==b自配对问题后，立刻把对拍逻辑固定下来，从此每次遇到枚举类题目都先跑一遍对拍。这个习惯帮我省下的时间，可能比我写过的任何题解都多。
最后再分享一个小技巧：在本地测试时，别只跑题目给的样例。自己构造几组边界数据，比如n=1、所有人体重都相同、体重分布极不均衡（一个人体重很大，其他人很小）、S取最小值和最大值等，把这些case跑通，心里就有底了。对于CF1399C，我强烈建议你亲手写一遍计数法，再写一遍双指针法，然后把两个版本对着跑随机数据，看到结果完全一致的时候，这道题才算真正吃透了。
