企业官网建设流程全解析

1. 题目到底在说什么：划船比赛的组队规则

CF1399C这道题，一般题解里都叫它“划船比赛”，是CF某轮Div.2的C题。第一次见到它的人，十有八九会以为是个贪心配对问题，但实际做下来会发现难点根本不在配对，而在你肯不肯把“共同目标和”枚举一遍。

题意其实非常短：给出一支队伍里每个人的体重数组，每个体重代表一个队的重量。现在要把所有参赛队两两组合上船，每艘船上正好两个人，而且所有船上的两个人体重之和必须等于同一个数s。问你最多能组成多少艘船。注意这里有个很容易忽略的细节：不是所有队伍都必须上船，某些队完全可以闲着，题目只是要最大船数。

这个题非常适合刚开始刷CF 1300到1500分段的选手，因为它考察的并不是复杂数据结构，而是“枚举隐藏参数”的思维。你以为它要用贪心或者二分，其实真正的解法简单得让人有点意外：把可能的s全部试一遍，每个s用双指针或计数桶扫一遍，取最大值就完事。那些绕了一大圈去想贪心策略的人，反而会把简单题做复杂。

下面从一个具体的输入样例开始，把这个题从头到尾拆开讲一遍。

1.1 输入输出到底长什么样

CF平台的题面一般不给中文翻译，所以我们先对着输入输出格式捋一遍。第一行是一个整数T，表示有T组测试数据。每组数据第一行是一个整数n，代表总的队伍数量，也就是体重数组的长度。第二行有n个整数，第i个整数w[i]是第i支队伍里队员的体重。

输出就一个整数，表示最多能组织的船数。每组数据输出一行。

举个例子：n=6，体重是 [1, 2, 3, 4, 5, 6]。我们要找共同体重和s。如果取s=7，可以把 (1, 6)、(2, 5)、(3, 4) 配成三艘船；如果取s=8，最多只能配 (2, 6)、(3, 5) 两艘；取s=5最多就只能配(1, 4)、(2, 3)两艘。所以正确答案是3。这个过程反映了一个本质：s的选择直接影响答案，而s又隐藏在题目里没有直接给出，所以第一步就是把它显式地变成枚举对象。

1.2 三个容易被忽略的边界条件

读题不仔细的人，经常会在以下三个地方翻车。

第一个，队伍不是全部都要用。比如n=5，体重全是1，s=2时只能配出两艘船，最后还剩一个队没法配对，但这没关系，因为答案是2，不是要你把五个人全塞进船里。

第二个，每支队伍只能出现在一艘船上，也就是每个体重数字只能用一次。这个看起来是废话，但在写计数桶代码时，如果忘记了“用掉的队伍要减掉”，就会搞出同一支队伍配两艘船的尴尬结果。

第三个，T组数据之间是独立的，每组的n和体重都可能不同，输出要各算各的。很多人第一组样例跑对了，第二组开始错，就是数组或者计数桶没有清空。

这些边界条件说出来好像没什么，但在紧张的做题过程中，它们往往是WA之后才被想起来的东西。

1.3 为什么第一反应不该是贪心

我见过很多人在讨论区抱怨：这题是不是可以“最重的配最轻的”？其实这个想法建立在一个隐含假设上，就是你提前知道了s应该是多少。可问题是s是未知的，而且局部最优的配对不代表全局最优。

举个反例：n=8，体重数组为 [2, 2, 2, 2, 5, 5, 5, 5]。如果按“最大配最大”的思路，先把5和5配，得到两艘体重和为10的船；再把2和2配，得到两艘体重和为4的船。但题目要求所有船的共同和是同一个s，10和4明显不是同一个数，所以这不是合法方案。可如果枚举到s=7，我们会发现 (2, 5) 可以配出四艘船，直接刷新答案。

这个例子说明，“先配对、再凑s”的顺序是错的。正确顺序应该是“先定s、再检查能配出多少对”。这也是整道题的核心突破口，下一部分详细讲。

2. 核心突破口：把共同体重和s当成枚举对象

一道题如果有一个未知参数，而这个参数的范围又很小，那么“枚举它”往往是性价比最高的做法。这题里的s就是这样一个参数，它的取值范围被体重范围死死限制住了。

体重w[i]的取值范围是[1, n]，所以两个人体重之和s最小是1+1=2，最大是n+n=2n。n最多只有50，所以s最多也就2到100，一共不超过99种可能。99种可能，每种都试一遍又能怎么样呢？这几乎就是明说“直接在s上暴力”了。

2.1 s的范围是怎么算出来的

在写代码之前，先把s的上下界确定清楚，这比代码本身更容易出错。

体重最小值是1，所以两个最轻的队配在一起，和的最小值是2。体重最大值是n，所以两个最重的队配在一起，和的最大值是2n。因此s的枚举范围是闭区间[2, 2n]。

有些读者可能会问，如果一组数据里根本没有体重为n的队伍，那s=2n这个值不是白枚举了吗？确实白枚举，但无所谓。暴力枚举的好处就在于多试一次不会错，最多只是cur的结果是0，ans不会受到影响。反过来，如果枚举上界写小了，比如只写到了2*max_weight，就可能漏掉答案，这种边界差一的问题非常坑。所以我的习惯是：能吃下2n就写2n，别自作聪明去缩范围。

2.2 固定s之后，问题退化成什么

一旦s确定下来，整个问题就从一个“全局优化问题”变成了一个“给定目标和的配对问题”。这句话可能有点抽象，我说细一点。

原问题是想找一个s，使得在“所有船的和都等于s”的约束下船数最多。这听起来像一个带约束的优化。但当s被枚举成一个常数时，约束变成了“所有船的和恰好等于这个常数”，于是我们需要回答的子问题只有一个：在这个体重数组里，最多能拿出多少对体重和等于s的数对。

这个子问题友好得多。它不再需要关心“如何平衡不同s之间的竞争关系”，只需要在一个固定的目标值下尽量多凑对子。而凑对子这种事，一看到就可以想到排序双指针，或者用计数桶去配对。两种做法都可以在O(n)或O(n/2)时间内完成。

为了更直观，我们可以算一下总复杂度。双指针版：排序O(n log n)，枚举99种s，每次花O(n)扫描，所以总复杂度约O(n log n + 99n)。n=50时，这个数字小到可以忽略。计数桶版干脆不需要排序，每个s只枚举到s/2，复杂度更小。即便T组数据最多有1000组，总操作量也就是百万级别，随便跑。

2.3 为什么这题不该执着于“最优算法”

说实话，我第一次做这题的时候，也纠结过“能不能O(n)一次性算出来”。后来想明白了：在竞赛里，“范围内暴力”本身就是一种正经算法，前提是你确认范围足够小。n≤50给了你一个巨大的暗示，那就是出题人就是想让你枚举s，看看你会不会在固定s后用双指针或计数桶检查答案。

这不是“没办法才暴力”，而是“数据范围允许的最优做法就是暴力枚举”。很多新手对O(n^2)有恐惧心理，但一个n=50的O(n^2)和一题n=10^5的O(n^2)完全是两码事。先看范围，再谈优化，这才是竞赛做题的正确姿势。

3. 两种实现都写了一遍：双指针和计数桶

很多题解只给一种写法，但我在训练的时候习惯把两种都写出来对比一下，因为它们的代码风格和适用场景不一样。下面分别给出C++实现，并解释每一段在做什么。

3.1 双指针版：排序后扫一遍

双指针的思路非常经典：先把体重数组排序，然后对于固定的s，用左指针指向最轻的队，右指针指向最重的队，根据二者之和与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 ans = 0; for (int s = 2; s <= 2 * n; s++) { int l = 0, r = n - 1; int cur = 0; while (l < r) { int sum = w[l] + w[r]; if (sum == s) { cur++; l++; r--; } else if (sum < s) { l++; } else { r--; } } ans = max(ans, cur); } cout << ans << '\n'; } return 0; }

核心在于双指针的移动逻辑。当w[l] + w[r] > s时，说明右指针指向的这个体重太大了，和当前最轻的左指针配对都超了，那它跟任何更重的左指针配对只会更大，所以必须把右指针往左移。当和小于s时，说明左指针的体重太小，需要往右移来增大和。只有和正好等于s时，才记录一对，然后左右指针一起收缩，因为这两个数已经被用了。

这里要特别强调：为什么双指针能保证求出最大对数？因为数组有序，每次只移动“当前情况下唯一可能凑出s”的指针，不会漏掉任何一端还能配对的数。这个结论在双指针题目里是通用的，很多题解会直接略过，但新手在这里最容易迷糊。

3.2 计数桶版：省掉排序，代码更短

双指针要排序，计数桶连排序都省了。具体做法是先统计每个体重出现的次数cnt[w]，然后固定s，枚举左半边的体重i，看它和s-i能凑出几对，取min(cnt[i], cnt[s-i])。

#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(105, 0); for (int i = 0; i < n; i++) { int x; cin >> x; cnt[x]++; } int ans = 0; for (int s = 2; s <= 2 * n; s++) { int cur = 0; for (int i = 1; i * 2 <= s; i++) { int j = s - i; if (j > 100) continue; if (i == j) { cur += cnt[i] / 2; } else { cur += min(cnt[i], cnt[j]); } } ans = max(ans, cur); } cout << ans << '\n'; } return 0; }

这个写法里最妙的一行是 for (int i = 1; i * 2 <= s; i++)。它的作用是只枚举体重组合中较小的一半，避免把(a, b)和(b, a)当成两对重复计算。当i和j相等时，比如体重都是3，共有cnt[3]个人，那么能配出的对数就是cnt[3] / 2，整除即可，剩下一个不用管。当i不等于j时，能配出的对数是较少出现次数的那一方，即min(cnt[i], cnt[j])，因为多出来的那一方只能闲着。

计数桶版本对“数组要清空”更敏感，因为cnt是每个测试组都可能变化的全局状态。我在代码里用vector每次新建，就不需要手动清空，这也是推荐的做法。如果非要用全局数组，记得每次循环开头memset。

3.3 两种写法怎么选

我自己做CF题的时候，多数情况下会选双指针，因为它的移动逻辑让我更容易确认没有重复计数；但如果时间紧，计数桶的代码更短，敲起来快。下面用表格做个对比，方便你按自己的习惯选。

如果你只是为了过这道题，两种都行。但如果你想锻炼双指针思维，建议先把双指针版写顺；如果你想在正式比赛里拼手速，计数桶版是更好的选择。两种都写一遍，收获最大。

4. 提交之后容易罚时的几个点

CF的C题，WA率其实不低，而且很多WA都是同一类原因：不是思路错，是手滑或者边界没管好。我把自己和身边人踩过的坑全部列出来，每条都是拿罚时买来的教训。

4.1 多组测试数据的“残留”问题

第一组样例对，第二组开始错，十有八九是数组没清空。特别是用全局int cnt[105]的时候，上一组数据留下的计数会影响下一组的s配对。比如上一组有5个体重3的人，下一组没有体重3的人，可cnt[3]还是5，算出来一个根本不存在的船队。

解决方案很简单：vector cnt(105, 0) 定义在while(T--)循环内部，每组自动重建。如果你喜欢全局数组，就写memset(cnt, 0, sizeof(cnt))，别偷懒。这个错误在CF上有一个典型特征：第一组输出正确，第二组开始偏大，而且偏大的程度和上一组数据有关。

4.2 s的枚举上界差一点

s从2到2n，这个上界有很多人写成2 * maxWeight，或者漏掉了n=1的情况。n=1时，只有一个队，无论如何也凑不出船，答案是0。双指针版里l < r不成立，自然返回0；计数桶版里s循环虽然跑了，但cur也是0。这一点问题不大。关键是上界：如果一组数据最大体重不是n，比如n=10，但体重最大只有3，那么s枚举到2n=20显然有很多无效情况，不过不影响正确性；反过来，如果你把上界写成2maxW，当体重的最大值确实等于n时结果一样，但当体重最大值小于n时，比如n=10、maxW=8、答案可能在s=16，而2maxW=16也没漏。真正危险的是你以为maxW一定小于n，结果某组数据里maxW刚好是n，而你枚举到2maxW-1之类的错误上界，就会漏掉答案。所以别省，就写2*n最稳。

4.3 计数配对时重复计算

这个坑主要出现在自己改写的计数桶代码里。如果循环写成for (int i = 1; i <= s - 1; i++)，然后对每个i都做cur += min(cnt[i], cnt[s-i])，你会发现答案几乎翻了一倍。因为i=2、j=5和i=5、j=2这两轮循环计算的是同一批配对，但cur加了两次。

正确做法是只枚举i <= j的那一侧。我个人喜欢用 i * 2 <= s 这个写法，它天然把i和j相等的情况也包含进来，让i永远不会超过j，不会重复。在这里“重复计数”不是小细节，而是能让你从一个WA卡到时间结束的死结。

4.4 又一次老生常谈：先看数据范围，再决定复杂度

这题的n≤50被很多人轻飘飘看过，但恰恰是它决定了“暴力枚举s”是正解。如果n=50，O(n^3)都能过；如果这道题改成n=10^5，那这个枚举所有s的思路就需要彻底重构。

我的建议是：拿到任何题，先圈出数据范围的限制，再想算法。尤其是CF的C题，数据范围往往会直接告诉你出题人想考什么。限制越小，暴力枚举的可能性越大。这不是什么高端技巧，而是做题顺序的问题，但偏偏很多人会忽略。

5. 从这题看一类“参数化配对问题”的通法

CF1399C做完之后，不要急着划走。它属于一个很大的题目家族：两个元素一组，某种运算结果要全部相等，求最大组数。我把这类题叫“参数化配对问题”，因为它们的共同核心都是有一个未知的共同参数需要枚举。

5.1 怎么一眼认出这类题

这类题的标志性特征有三个。第一，输入是若干元素，要求两两组合。第二，组合后有一个共同的运算目标值，这个值是未知的，可能是和、差、乘积、异或等等。第三，要最大化成功组合的组数。只要同时满足这三条，基本就可以往“枚举目标值”的方向想。

比如常见的“给一串数，两两配对使每对的和都相等，求最多配对数”，本质和这题一模一样。甚至很多题目还把s直接明确给出，那就更简单了，连枚举都省了，直接固定s做双指针。

5.2 通法三步走

这类题我总结了一个三步模板，CF1399C就是它的标准执行样例。

第一步，根据数据范围确定目标值的上下界。和的上下界是[2, 2n]，差的上下界是[-(max-min), max-min]之类的，反正把可能区间算出来。第二步，枚举这个目标值。第三步，对每个目标值用双指针、哈希表或计数桶检查最多能配几组，取最大值。

这个模板听起来平淡，但它能解决大量Div.2的C题和一部分D题。关键在于第三步的检查方法要选对：能排序就双指针，值域小就计数桶，值域大就哈希表。

5.3 如果n变大，这题还能怎么变

把n改成10^5、体重范围改成10^9，这题就会变成一道完全不同的题。枚举2n个s不再可行，因为2n已经是210^5，如果再乘n等于210^10，直接超时。

这时候的优化思路有两个方向。一是只枚举“可能会产生配对的s”，比如只枚举每个体重与每个体重之和，但要去重；二是用FFT/NTT做卷积，把所有体重两两之和的频次分布一次算出来，再对每个s用频次配对。第二种方法对新手来说有点遥远，但知道有这条路就行。这也说明，CF1399C作为一个C题，给n=50是有意为之的，它想让新手先掌握枚举这一基本武器。

5.4 实战建议和调试技巧

最后聊一点刷题过程中的操作建议。第一，做题顺序上，先自己造几个样例手算，再写代码。特别是n=1、所有体重相同、体重成等差数列这三种情况，很容易暴露代码里的边界错误。第二，提交之前先跑一遍“s=2”和“s=2n”这两个端点，看看有没有越界。第三，如果WA了，不要东改一行西改一行，直接造一个小数据，用暴力枚举所有配对方式的方法做对拍，找出第一个不同的s，问题范围就能瞬间缩小。

我在实际做题中还有一个习惯：AC之后故意把代码改错几个常见点，比如i*2<=s改成i<=s-1，再交一次看看会不会WA。这样做能让自己更清楚哪些地方是“碰巧对”的，哪些地方是“理解后写对”的。

CF1399C这道题的代码量不大，但它把“枚举隐藏参数”这个思维教得很透彻。很多一开始觉得无从下手的题，一旦想到“把没给的那个数当成枚举对象”，思路就会瞬间打开。下次遇到看起来需要贪心但怎么贪都不对劲的题，不妨先问问自己：有没有一个隐藏的、范围很小的参数可以枚举？如果答案是肯定的，那就别犹豫，直接爆力枚举它。