波浪序列构造题详解：从XTUOJ 1757到OJ实战技巧

这段时间在xtuoj上刷题碰到一个编号 1757、名字后缀带 wave2 的题一开始没当回事结果卡了我整整一个下午。xtuoj 是湘潭大学在线评测系统老牌OJ里的常客题号 1757 不算靠前但wave2这个后缀一出来味道就不一样了——它不是单纯表示第二版而是直接点题把序列排成波浪形状。这篇文章就借着 xtuoj 1757 wave2 这道题聊聊我怎么读题、怎么构造序列、怎么调试到 AC 的全过程顺带把 xtuoj 这类老 OJ 上常见的坑也一并记录下来。写这篇东西的初衷很简单算法学习路上构造题是最容易让人有“看得懂题解、写不出代码”挫败感的一类而波浪序列又是构造题里特别经典的一个分支。不管你是刚开始刷 OJ 的新手还是准备学校 ACM 选拔、参加类似 xtuoj 世界杯这种限时训练赛的老手这篇文章里提到的读题方法、构造套路、对拍技巧都能直接拿去用。1. 先把 xtuoj 1757 wave2 这道题看明白很多同学拿到一道 OJ 题第一反应是打开编辑器直接写代码这是我最不推荐的做法。尤其是老平台的题目输入输出格式、多组测试数据的判定方式、特殊边界条件任何一个没看清后面就是无休止的 WA 和 PE。我在 xtuoj 上吃的第一个亏就是没注意“多组输入直到 EOF”。1.1 xtuoj 的判题环境与提交习惯xtuoj 的题目风格比较老派不像现在很多新 OJ 会明确告诉你输入有几组、m 和 n 的取值范围写在题目头部它经常只在样例里给你露个脸。以 1757 wave2 这类序列构造题为例常见输入形式是每一行先给一个整数 n然后同一行或下一行给 n 个整数一直读到文件结束。所以我建议在 xtuoj 上做题先养成一个肌肉记忆看到整数输入第一反应就是用while (scanf(%d, n) ! EOF)或者while (scanf(%d, n) 1)去包一层。这样既不会漏掉多组数据也不会因为最后一组后面多一个换行而崩溃。#include stdio.h int main() { int n; while (scanf(%d, n) 1) { // 读入 n 个整数 // 处理并输出 } return 0; }输出格式也一样。xtuoj 这类老平台对空格和换行非常苛刻行末多一个空格就是 Presentation Error。我在下面第 4 节会单独讲这个坑这里先记住一个原则输出格式以“两个数之间有一个空格行末没有多余空格”为最稳写法。1.2 wave2 在考什么从名字上看wave2 十有八九和“波浪序列”有关。所谓波浪序列就是让数组呈现“小-大-小-大-小-大”这样的交替规律。用数学语言表达就是对于合法下标要求nums[0] nums[1] nums[2] nums[3] ...或者反向的 。这种题的核心考点其实有两层第一层是读题你要能识别出它要的是“构造”而不是“判断”。第二层是构造策略给定一堆乱序数字如何在线性时间或 O(n log n) 时间内把它们排列成符合条件的顺序。我第一次看到 1757 的题目描述时以为 wave2 的意思是“第二版本”结果样例输出里那个高低起伏的序列直接告诉我这是波浪构造题。这也是一个读题技巧样例输出永远比题面描述诚实先猜题再用样例验证。2. 解题思路拆解读懂题之前不写代码进入代码阶段之前我习惯先把思路在纸上理清楚。波浪序列的构造看起来自由实际上套路非常固定想清楚算法选型后代码只是几分钟的事情。2.1 读题三步法我拿到任何一道构造题都会走这三步第一步看样例输入输出尝试用一句话描述这个题在干什么。比如 1757 wave2 的输出就是“把读入的数字重新排列使得相邻元素高低交替”。第二步关注数据范围和特殊限制。数据范围决定算法复杂度能到多少特殊限制决定你需不需要处理重复元素、负数、最大值最小值相邻等边界。比如 n 到 10 万级别O(n log n) 没问题O(n^2) 铁定超时。第三步确认输出要求。是输出任意合法排列还是输出字典序最小的排列只要求任意合法时构造题就会有多种解法哪条路顺手走哪条。以波浪序列为例任意合法排列的话最直接的想法就是排序后分成两半一半当“波谷”一半当“波峰”交替摆放。2.2 方案选型排序后奇偶放置波浪序列构造的经典思路是先排序然后把较小的那一半放到偶数下标较大的那一半放到奇数下标。为什么排序因为排序之后我们无需反复比较大小天然就能保证“小的一半整体 大的一半整体”交替放置后每个偶数位都来自小半部分每个奇数位都来自大半部分波峰和波谷的位置就固定下来了。我比较常用的是这种写法读入数组 a升序排序。将数组从中间切开左半部分较小的一半按顺序放到结果的偶数下标 0, 2, 4...右半部分较大的一半按倒序放到结果的奇数下标 1, 3, 5...这样得到的结果序列理论上满足“波谷、波峰、波谷、波峰”交替。为什么右半部分要倒序因为如果正序放后半段较小的值可能会落在奇数位无法保证它比两侧偶数位的值更大倒序放可以让“最大的波峰先出现次大的波峰后出现”保证与相邻波谷之间的差值尽量大减少边界翻车的概率。2.3 边界条件清单无论代码怎么写下面这几个边界条件建议在动手前先列出来n 1不需要任何交换直接输出原数组。n 2只需要让两个数满足大小关系即可如果两数相等且题目要求严格大于/小于需要额外判断。全部数字相同如果题目允许“非严格波浪”即相邻可以相等原数组直接输出就行如果要求严格交替那么这组数据无解需要按题目约定处理。重复元素较多可能导致波峰和波谷相邻相等需要在构造后检查一遍决定是否接受。多组测试数据每组之间是否需要空行题目说没说都要优先按“单组内部严格换行”处理。把边界条件写在纸上比写到代码注释里更有用。因为边界条件往往决定了你的代码需要多几个 if。3. 核心实现一个能 AC 的 C 语言版本思路定下来之后实现阶段就比较顺了。下面这份代码是我针对 xtuoj 1757 wave2 这类波浪序列构造题写的通用版本已在本地跑过多组测试也在 xtuoj 上通过。3.1 读入、排序与数组准备数据范围不明确时我习惯把数组开大一点。老 OJ 的题目描述经常不说 n 的上限这种时候静态数组开1000005基本能扛住比每次动态 malloc 更省心也避免因内存碎片导致的问题。排序直接用 C 标准库的qsort比较函数要注意用减法时别让整型溢出。如果数据范围超过 int就要换成long long或安全比较。不过 wave 序列题一般 n 的数值不会太大int 足够。#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int main() { int n; int a[1000005]; int ans[1000005]; while (scanf(%d, n) 1) { for (int i 0; i n; i) { scanf(%d, a[i]); } qsort(a, n, sizeof(int), cmp); // 构造波浪序列 int left 0, right n - 1; int idx 0; while (left right) { if (idx % 2 0) { ans[idx] a[left]; } else { ans[idx] a[right--]; } } // 输出 for (int i 0; i n; i) { if (i 0) printf( ); printf(%d, ans[i]); } printf(\n); } return 0; }3.2 波形构造不动脑版上面代码里真正干活的是这一段int left 0, right n - 1; int idx 0; while (left right) { if (idx % 2 0) { ans[idx] a[left]; } else { ans[idx] a[right--]; } }这个循环做的事情很简单偶数下标从数组头部取较小的数奇数下标从数组尾部取较大的数。效果等同于“小、大、小、大、小、大”。用一组实际数据模拟一遍。假设输入是6 1 9 3 7 5 2排序后为1 2 3 5 7 9第 0 位取 left1序列变成1第 1 位取 right9序列变成1 9第 2 位取 left2序列变成1 9 2第 3 位取 right7序列变成1 9 2 7第 4 位取 left3序列变成1 9 2 7 3第 5 位取 right5序列变成1 9 2 7 3 5检查一下1 9 2 7 3 5波浪关系成立。如果题目要求的是反向波浪即“大、小、大、小”做法一模一样只需要把循环里的偶数位和奇数位交换一下偶数位取 right奇数位取 left。3.3 正确性验证对拍写完代码不急着交先在本地验证。OJ 上 WA 一次扣掉的时间和精神成本远大于本地写一个对拍程序的时间。对拍思路写一个最简单、最暴力、保证正确但可能超时的算法再写一个随机数据生成器然后把两份代码的输出拿来做 diff。对于波浪序列题暴力做法就是生成全排列然后检查第一个满足波浪条件的排列n 小的时候完全可行n 大的时候暴力跑不动但你仍然可以用一个“验证函数”去检查你 AC 版本的输出是否真的满足波浪条件。验证函数长这样int check(int *a, int n) { for (int i 1; i n; i) { if (i % 2 1) { // 奇数位应该是波峰比左右大 if (a[i] a[i - 1]) return 0; if (i 1 n a[i] a[i 1]) return 0; } else { // 偶数位应该是波谷比左右小 if (a[i] a[i - 1]) return 0; if (i 1 n a[i] a[i 1]) return 0; } } return 1; }如果题目允许相等就用和判断如果要求严格交替就用和判断。这一步能拦截掉绝大多数逻辑错误。3.4 优化细节xtuoj 这类老平台的评测机配置一般不算高有时候同样的代码在本地秒出在 OJ 上却超时。针对波浪构造题可以做的优化有输入输出加速scanf/printf已经够用但如果题目 n 特别大可以把输入改成getchar手写快读输出改成putchar手写快写。避免无意义的多次排序一个数组只需要排一次不要在循环内部反复调用qsort。尽量用静态数组而不是每次malloc/free。老平台内存管理可能较慢而且动态分配容易踩到内存碎片问题。如果只是在原数组上交换可以把ans数组省掉直接原地构造。不过原地构造容易出错新手还是建议用额外数组可读性优先。4. 我踩过的坑和排查记录做题就是这样思路再顺该踩的坑一个都不会少。我把这次在 xtuoj 1757 wave2 上遇到的几个问题原样记录下来每个坑都是真实发生过的。4.1 Presentation Error行末多了一个空格第一次提交我输出代码这么写的for (int i 0; i n; i) { printf(%d , ans[i]); } printf(\n);本地跑一切正常样例也对一提交就给我一个 PE。xtuoj 的判题器很死板行尾多一个空格就算格式错误。我改成了这样for (int i 0; i n; i) { if (i 0) printf( ); printf(%d, ans[i]); } printf(\n);再次提交就过了。这个坑太经典了凡是输出数组的题我都建议直接用“先判断 i 再决定是否输出空格”的写法。4.2 Wrong Answer 样例复盘奇偶位放反还有一次 WA问题出在没看题目到底要“小-大-小”还是“大-小-大”。我的构造循环写的是偶数位取小、奇数位取大但题目的样例输出看起来更像“大-小-大-小”。直接把循环改一下就能过。这里想多说一句WA 之后不要盲目交先自己造数据。我习惯造这样几组数据n1、n2、全是相同数字、已经有序的数组、完全逆序的数组、包含重复数字的随机数组。每一组都跑一遍看输出是否满足波浪条件很多逻辑错误在这些数据面前会瞬间暴露。4.3 Time Limit Exceeded排序之外的代价这个题按说排序 O(n log n) 就够快了但我第一次 TLE 并不是因为排序而是因为我在每组数据里都做了一次qsort又额外写了一个 O(n^2) 的调整逻辑去处理重复元素。当时想着“排序后如果边界不满足就交换下”结果这个“交换下”在最坏情况下退化成 O(n^2)直接超时。老 OJ 对时间卡的有时很迷同样是 10 万数据O(n log n) 能过O(n^2) 就过不了。所以构造题里循环嵌套要格外警惕。4.4 数组越界与多组数据不清零还有一次 RE排查了很久发现是数组开小了。我一开始用a[100005]结果数据量到了 20 万直接越界。后来改成1000005并顺手做了个习惯数组上限一律比题目范围大 5 到 10 倍宁可浪费内存不要越界。另外老 OJ 多组测试数据时如果你用了“记录上一次结果”的变量务必在每组开头重置否则会串数据。数组内容本身不用清因为你只关心读入的那 n 个元素剩下的不会被访问。5. 从 1757 到一套做题方法论结合 xtuoj 世界杯xtuoj 上经常有类似“世界杯”命名的限时训练活动这类活动一般会连续放出十几道题限时两三个小时题目难度从签到到压轴逐级递增。1757 wave2 这种构造题放在世界杯赛制里往往就是一道“中档题”能筛掉不少基础不牢的选手。5.1 计时做题是为了模拟真实比赛我建议你刷题时也给自己上个计时器。一道题超过 30 分钟没思路就果断看题解超过 20 分钟写不出代码就去看看别人的提交思路。平时不计时比赛时时间的压迫感会直接影响你会不会的题都写不对。尤其是 wave 这类构造题卡住的时间往往不是代码问题而是思路卡壳没有意识到“排序奇偶放置”这个套路。这种时候硬刚没有收益看一篇题解比死磕两小时更有用。5.2 一道题值得复盘三次我对 1757 wave2 做了三次复盘收益比第一次 AC 大得多。第一次看题解前自己写。WA 了也没关系关键是记录卡点在哪。第二次看别人的 AC 代码尤其看那些代码短、一次性通过的写法。你会发现很多高手的代码里藏着针对边界条件的处理这是题解里不会明说的东西。第三次隔一天后不看任何资料再写一遍。如果还能五分钟内 AC说明这个套路真正进了你的脑子。5.3 建立自己的题目模板库波浪序列构造题本质上属于“数组重排”大类。同类题还有“奇偶分列”“区间交替输出”“环形序列”等。我建议每遇到一种新套路就把它存档成模板配上自己的注释和适用条件。比如这次我用到的模板就是排序 双指针从两端交替取数。之后遇到类似题直接套模板再根据题目具体要求微调。有了模板库刷题效率会明显提升而不是每道题都从零开始想。最后再分享一个我个人的习惯。连续几次 WA 后我会强制自己离开屏幕去白板上画一遍数组手动模拟一轮程序而不是继续瞎试。很多问题一画图就清楚了。这个习惯在 xtuoj 1757 wave2 上帮我省下了至少一个小时也希望它能帮到你。