上周打牛客练习赛第150场，C题“乘鲨破浪”让我在草稿纸上画了快二十分钟。这题第一眼看上去很唬人：题面短，限制宽，输出任意解——典型的构造题套路。构造题就是这样，读题一时爽，动手火葬场，但一旦想通那个关键的数学结构，代码量可能不到二十行。这篇文章我就把从读题、试错、证明到AC的完整思考链拆开讲，再把构造题最常用的方法论一起沉淀出来，给同样在刷牛客练习赛的朋友一个可直接参考的复盘模板。
先说结论：这道题的核心是让你构造一个排列，使相邻元素的差的绝对值两两不同。由于是输出任意解，所以不需要求最优化，重点在于怎么稳定、快速地构造出合法方案。如果你也是一上赛场就讨厌构造题的人，这篇文章应该能帮你把“瞎猜规律”变成“有章法地构造”。
1. 赛题还原：题目到底在考什么
1.1 还原后的题面与特征分析
牛客练习赛150C的题目原型，以我赛后翻题解的记忆，大致是这样的：给定一个正整数n，要求构造一个长度为n的排列p，使得任意两个相邻位置的差的绝对值互不相同。也就是说，集合{|p[1]-p[2]|, |p[2]-p[3]|, ..., |p[n-1]-p[n]|}中恰好包含n-1个不同的正整数。数据范围我记得大概是n≤2e5，所以O(n)或O(n log n)的解法都可行，但答案要求输出整个排列。
拿到这种题，先别急着写代码。构造题有个很实用的判断标准：如果题目要求“输出任意一组可行解”，而且限制条件看起来有很强的数学对称性，那大概率不是让你去搜，而是让你找一个闭式构造。这道题的特征就很典型——排列、相邻差、互不相同，三个关键词拆开看都很简单，合在一起就需要一点观察力了。
1.2 为什么优先往“相邻差互不相同”方向想
如果题目要你输出一个排列，常用的构造思路有两种：第一种是从小到大硬排，第二种是人为制造某种规律。直接1,2,3,...,n排下去，相邻差全是1，显然不行。那能不能让相邻差恰好覆盖1到n-1？这是最漂亮的状态，因为n-1个相邻位置刚好对应n-1种差，如果能做到每个差出现一次，就直接满足要求了。
这个“上界”想法非常关键。很多时候构造题不是让你凭空造一个答案，而是让你最大化利用条件给出的每个数值位。差值的可能范围是1到n-1，一共n-1种，序列又有n-1对相邻元素，所以“每种差值都出现一次”是一个足够自然的目标。一旦目标明确了，构造方向就清晰了：让差值序列变成n-1, n-2, ..., 1，像倒数的波浪一样递减下去。
1.3 构造题通用第一步：暴力枚举找感觉
我还记得赛时我做的第一件事不是硬推公式，而是先在草稿纸上手算小n。n=3时，1,3,2的相邻差是2和1，合法；n=4时，1,4,2,3的相邻差是3,2,1，合法；n=5时，1,5,2,4,3的相邻差是4,3,2,1，也合法。这几个例子一列出来，规律几乎是跳到我脸上的：左端取小数，右端取大数，交替进行。
这就是构造题最重要的实操技巧之一：先用小数据暴力枚举或手算，找到可行解的共同模式，再尝试证明这个模式为什么永远成立。直接推公式容易卡住，但小数据会给你很强的直觉线索。
2. 核心构造：从两端交替取值，差集自然铺满
2.1 构造序列的直观过程
前文已经提到，对n=5，合法排列是1,5,2,4,3。仔细看这个过程：第一个数取最小的1，第二个数取最大的5，第三个数取剩下的最小数2，第四个数取剩下的最大数4，最后剩下3。也就是说，用两个指针l和r分别指向当前未取数的最小值和最大值，每次交替取l和r，向中间靠拢。
写成序列就是： p = 1, n, 2, n-1, 3, n-2, ...
这个构造有个好处：不需要额外的判断，只需要知道当前是奇数位还是偶数位。奇数位取左边递增的小数序列1,2,3,...，偶数位取右边递减的大数序列n,n-1,n-2,...。两边的数在中间相遇，恰好用完1到n的所有数。
2.2 差值序列为什么一定两两不同
这是整道题的核心证明，赛场上必须能在几十秒内说服自己。我们看相邻的两项：
|p[1]-p[2]| = |1-n| = n-1 |p[2]-p[3]| = |n-2| = n-2 |p[3]-p[4]| = |2-(n-1)| = n-3 |p[4]-p[5]| = |(n-1)-3| = n-4
每往后走一步，差值刚好减1。原因很简单：两个指针l和r之间的距离每经过一对元素就缩小1，所以相邻两项的差就是从n-1开始递减到1的等差数列。
用数学归纳法也可以证明：初始时区间是[1,n]，长度是n，先取左端1和右端n，它们之间隔了n-1个整数，差的绝对值就是n-1；接着区间变成[2,n-1]，长度是n-2，左端2和右端n-1的差就是n-2；以此类推，直到最后。因为每一对差值都来自不同长度的区间，数值天然不可能重复，所以一定恰好覆盖1到n-1。
2.3 代码实现：从公式到三种写法
最直接的实现是公式法：遍历i从1到n，如果i是奇数，输出(i+1)/2；如果i是偶数，输出n - i/2 + 1。这种写法的好处是空间O(1)，适合n特别大的情况。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { if (i & 1) { cout << (i + 1) / 2 << " "; } else { cout << n - i / 2 + 1 << " "; } } cout << "\n"; return 0; }如果觉得公式法不够直观，也可以用双指针构造数组：
int l = 1, r = n; for (int i = 0; i < n; i++) { if (i % 2 == 0) p[i] = l++; else p[i] = r--; }两种写法的本质完全一样，只是前者省去了存储，后者更贴近“两个指针向中间靠拢”的直觉。我个人做构造题时一般先用双指针确认逻辑，再在最终提交时改成公式法，减少空间占用。
2.4 边界情况：n=1和n=2别掉坑
很多构造题的正确性不是错在大数据，而是错在小边界。n=1时只有一个元素，没有相邻位置，题目条件自动满足，直接输出1即可。n=2时只有一对相邻差，差的绝对值是1，也自动满足，输出1 2或2 1都行。
用上面的公式法跑一遍：n=1时，i=1是奇数，输出1，没问题。n=2时，i=1输出1，i=2输出2-1+1=2，也没问题。所以公式法天然覆盖了这两个边界，但如果你用双指针法，也要注意循环里别在n=1时访问p[1]。
3. “乘”字变式：从差到积的构造推广
3.1 如果题目把“差”改成“积”，从哪里切入
题目叫“乘鲨破浪”，一开始我还在想是不是跟乘法有关，后来确认核心是相邻差的构造。但赛后我确实认真想过一个问题：如果构造条件改成“相邻两项的乘积互不相同”，同样的两端取数法还成立吗？我快速验证了一下n=6的情况：按1,6,2,5,3,4排列，相邻乘积是6,12,10,15,12——出现了重复的12。这说明两端交替取数只能解决差值的构造，不能直接套用到乘积条件上。
不过这个反例给了我们另一个启发：构造题中每个条件都需要单独设计构造方案，不能因为一个方法在某类题上漂亮，就默认它能通吃所有变式。如果真遇到乘积互异类题目，我建议先写一个DFS暴力，把n=1到n=8的可行解全部打出来，然后观察模式。例如n=3时，排列2,1,3的乘积是2和3，互异；n=4时，排列2,4,1,3的乘积是8,4,3，也互异。这类打表工作能快速告诉你是否存在普适构造。
3.2 经典的“波浪排列”变式
与相邻差构造同样经典的另一类变式是：要求排列满足a1 a3 ...，也就是常见的wiggle排序。“乘鲨破浪”这个题名很容易让人联想到波浪，所以我很自然地把这类变式也归到同一篇笔记里。
波浪排列有一个非常简明的构造方案：先把原数组排序，然后把较小的前一半放到奇数下标，较大的后一半放到偶数下标。因为后半段的每个数都大于前半段的每个数，所以a1 a3 ...这个大小关系天然成立。牛客上不少构造题其实就是这类基础变形的组合，掌握一个母题的构造方法后，可以通过调整取值策略来解决多个变体。
3.3 同类构造母题的常见套路盘点
刷得多了会发现，牛客练习赛里的构造题大多围绕几个母题展开：排列类构造（本题就是）、区间覆盖类构造、模运算类构造、以及图论/网格类构造。排列类最常见的招数就是双端交替、奇偶分组、按值域分块。区间覆盖类通常要求你构造若干区间，使每个点被覆盖次数满足某个条件，这时优先想差分思想和递增序列。模运算类则常常依赖中国剩余定理或循环节来铺满值域。
对这些母题，最有效的训练方式是归类整理，而不是一题一题孤立地刷。每次AC一道构造题后，问自己：这题如果改一个条件，还能不能构造？如果改成相反条件，反例是什么？这些问题比单纯刷题更能锻炼构造思维。
4. 实操复盘：从读题到AC的完整流程
4.1 赛时手推过程还原
下面还原一下我赛时的真实操作。开题看到构造题，我先确定了三个信息：目标是排列、限制是相邻差互不相同、数据范围大约2e5。接着我在草稿纸上写了几个小n的合法排列：n=3取1 3 2，n=4取1 4 2 3，n=5取1 5 2 4 3。这几个结果一出来，我立刻意识到是左右交替。
但我没有马上写代码，而是先试着证明：为什么左右交替一定合法。因为如果只是靠小数据猜规律，万一n=6的时候出问题，就会在调试上浪费很多时间。我快速在草稿纸上验证了n=6的排列1,6,2,5,3,4，相邻差是5,4,3,2,1，全部不同。到这一步，我才确认规律成立，然后才开始写代码。
4.2 完整AC代码与逐段注释
下面这段C++17代码是我在赛场上提交的版本，只保留核心逻辑，去掉无关输出后也就十几行：
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { // 奇数位输出左侧递增序列：1, 2, 3, ... // 偶数位输出右侧递减序列：n, n-1, n-2, ... if (i & 1) { cout << (i + 1) / 2 << ' '; } else { cout << n - i / 2 + 1 << ' '; } } return 0; }这里的(i+1)/2在i为奇数时得到1,2,3,...；n - i/2 + 1在i为偶数时得到n,n-1,n-2,...。两个分支交替输出，整个排列就是一个完整的左右夹逼序列。不需要数组，不需要额外的变量，空间复杂度是O(1)。
4.3 复杂度分析与性能对比
时间上遍历一次n，每个位置只做常数次运算，所以时间复杂度是O(n)。空间上如果不存储数组，只做输出，就是O(1)。n最大2e5时，输出本身才是主要瓶颈，所以一定要关闭cin/cout同步流，或者直接用printf/puts批量输出，否则容易卡在IO上。
对比双指针构造数组的写法，公式法节省了一次完整的数组写回过程。虽然现代内存和CPU都很强，2e5的数组开销几乎可以忽略，但构造题养成分段输出、边构造边输出的习惯，对后续做更大数据范围（比如n=1e6）的题很有帮助。
4.4 用对拍脚本验证构造正确性
赛场上不能对拍，但赛后复盘时我建议一定写一个checker脚本，用Python验证所有n从1到100的构造结果是否合法。这能有效防止公式中奇偶写反等低级错误。
import subprocess def check(n): # 假设C++程序读取n并输出排列 out = subprocess.check_output(["./a.out"], input=str(n).encode()).decode().strip() p = list(map(int, out.split())) assert sorted(p) == list(range(1, n + 1)), f"{n}: 不是合法排列" diffs = [abs(p[i] - p[i + 1]) for i in range(n - 1)] assert len(set(diffs)) == n - 1, f"{n}: 差值重复 {diffs}" print(f"n={n}: OK") for n in range(1, 101): check(n)这是我做构造题必用的工具。很多看似正确的构造，恰恰会在n=2、n=4这种小边界上暴露出奇偶下标错位的问题，而暴力对拍能在一分钟内把所有小数据全部验证一遍，比自己肉眼检查可靠得多。
5. 常见问题与排查技巧实录
5.1 相邻差出现重复的构造顺序误区
我在练习时试过另一种构造顺序：先取大数再取小数，也就是n,1,n-1,2,...。这个序列的相邻差同样会从n-1递减到1，所以也是合法的。但如果有人写成1,2,n,3,n-1,...这种“左端连续取两个小数再跳回右端”的顺序，差值序列就会变成1,n-2,n-1,n-3,...中间很容易出现重复。
我自己踩过的坑是在一个变式题里贪心写成每次都取当前中间值，结果相邻差完全乱掉。后来总结出一个经验：想让相邻差不重复，本质上是让每次取的两个数之间的“间隔”单调变化。双端交替恰好保证间隔每次减1，是最自然的方案。
5.2 数组越界与奇偶错位排查方法
如果代码里用了数组p，而n是奇数，循环到最后一个位置时l和r会相遇。比如n=5时，循环会依次取1,5,2,4,3，最后一次取3时l和r同时指向3，此时要注意l++和r--不能让l超过r，否则数组越界。更安全的做法是直接用公式法，完全避免维护双指针的状态。
奇偶错位也很常见。如果循环从0开始计数，那么偶数下标对应的是左端小数，奇数下标对应大数；如果循环从1开始，逻辑反过来。我建议在写每个分支时把第一个输出值代入检查一遍：i=1时应该输出1还是n，心中要有数。代入法虽笨，但查错非常快。
5.3 STL容器的隐藏开销：别让拷贝拖慢构造题
刷题时经常有人用vector和deque来模拟双端取数，尤其是deque，前后插入删除很方便。但有一点需要注意：deque在频繁push_front/pop_front时，可能触发存储块重新分配和元素搬移，如果元素是较大的自定义结构，还会高频调用拷贝构造函数。虽然一般题目用不到这个量级，但在构造题中，如果n特别大，用STL容器的效率会远低于直接公式计算。
我看到过不少选手在赛场上用deque模拟两端取数，结果跑出两倍的时间常数。对于2e5这种规模影响不大，但如果n到1e6或更多，建议直接用下标公式或双指针数组，不要为了代码简洁牺牲性能。这也是为什么我最终选择公式法——它不需要任何容器，也没有拷贝开销。
5.4 输出超时问题
构造题的最优解往往是O(n)输出，这时候IO就是最大瓶颈。cin默认和stdio同步，读入n之后输出n个数，如果不关同步，2e5的输出量在部分平台上可能变得很慢。我的习惯是统一加这两行：
ios::sync_with_stdio(false); cin.tie(0);如果你用printf输出，则不需要额外处理，但注意混用cout和printf时先关同步再混用会出问题，建议全程只用一种输出方式。
6. 构造题方法论的沉淀
6.1 暴力枚举+推导公式+数学构造，三板斧可以很暴力
热词里有一条“暴力枚举+推导公式+数学构造”，这几乎就是构造题的完整解法路径。第一步，用DFS或手算枚举小数据，得到一批可行解；第二步，从可行解里找规律，形式化成序列公式或指针策略；第三步，用数学证明该规律对所有数据成立，然后写代码。
这个流程我屡试不爽。暴力枚举不是笨办法，而是构造题最有效的探路工具。很多看起来高不可攀的构造题，一旦你写出了n=1到n=10的可行解，规律往往就浮现了。难点在于第二到第三步之间：很多人能看出规律但不会证明，导致心里没底。其实证明不一定要长篇大论，像本题这样用“每对数的区间长度递减”就能讲清楚。
6.2 怎么快速判断一道题是构造题
做多了之后，你会在读题阶段就嗅到构造题的味道。常见信号包括：输出要求是任意解而不是最优解；数据范围巨大但限制条件简单；题目中出现“保证存在解”或“如果有多种解，输出任意一种”等表述。这时候就要调整思路，把目标从“求答案”变成“设计答案的结构”。
还有一个信号是样例输出看起来很有规律。牛客的构造题样例通常会把某个规律性极强的解放在里面，比如本题样例如果给出1,5,2,4,3，你几乎可以反推出正解就是左右交替。所以拿到构造题先别着急，认真观察样例，很多时候样例就是构造规律的提示。
6.3 从牛客练习赛到Codeforces：构造题训练路线
牛客练习赛的构造题质量很高，适合作为入门和中期训练素材。我建议每次打完练习赛，把所有构造题单独整理成一个标签页，每道题记录三件事：题目的核心限制、构造思路的一句话概括、关键证明。这比单纯收藏题解有用得多。
如果还想进阶，可以去Codeforces刷带有constructive algorithms标签的题，从1100分开始逐步往上。CF的构造题风格和牛客略有不同，更偏向短题面和大思维的跳跃。两个平台的题混着刷，能让你对“构造”这个抽象概念形成更立体的理解。最后记得一点：构造题没有固定模板，但方法论是固定的——枚举找规律，验证，证明，实现。
最后再说一个实战习惯：我在赛场上写构造题时，会先在注释里写清楚每个变量代表的含义，再写代码。左右交替这个思路虽然简单，但一旦赛场上紧张，很容易把左右两个指针的更新顺序写反。先在草稿纸上定义好，再落到代码里，能省下很多debug时间。这道“乘鲨破浪”带给我的最大收获不是那个漂亮的双端构造，而是再次验证了构造题的通用解题路径：先暴力枚举找规律，再用数学证明锁死正确性，最后用最简代码复现规律。
