考过PAT甲级的人应该都有这种感觉有些题看着不难AC率也还行但真上了考场总会在意想不到的地方卡住。Perfect Sequence就是这么一道典型题目25分的分值不算低但考察的点非常集中排序、双指针、二分查找外加一个不那么显眼但足以让人翻车的数据范围问题。我第一次做这道题是在准备PAT甲级的时候当时自认为“序列题”已经刷得够多了结果第一次提交就惨遭TLE。后来回头复盘才发现不是思路错了是对题目条件的理解不够深选错了实现策略。这篇就把我完整做题、优化、复盘的记录整理出来希望能帮到正在刷PAT甲级和类似题型的你。1. 读题时容易忽略的两个关键细节Perfect Sequence的题目描述并不长给定一个正整数序列和一个正整数p要求从序列中找出尽可能多的数组成一个“完美序列”定义是在这个子序列中最大值M和最小值m要满足 M ≤ m × p。最终要输出的就是能组成的最大元素个数。这里有几个值得注意的点恰恰是很多人在读题时一带而过的地方。第一个细节这里说的“从序列中找出一组数”并没有要求这些数在原序列中连续也没要求按原顺序排列。换句话说你完全可以把序列排序之后再挑这是解决这道题的核心前提。很多人一开始把问题理解成“找连续子数组”这个问题难度就完全不一样了而且样例数据弱的话很容易带偏思路。第二个细节是p的取值范围题目给的是正整数但没说p一定大于等于1。虽然从“正整数”这个定义来说p当然可以是1而且p1的时候结果一定是1因为序列中不同数字之间只要存在严格大小差异M m就必然导致M m×1不成立。这个特殊情况本身不难但它提醒了一件事边界条件往往藏在最不起眼的描述里。还有一个容易被忽略的点是数值大小。N的上限是10^5而序列中每个数的上限是10^9p的上限也是10^9。这意味着什么m × p这个乘法一旦做出来数值范围是10^18量级已经超出了int的表示范围。所有用int去存乘法结果、或者用int去写比较逻辑的C/C代码都会在这一步栽跟头。这一点我后面会专门说因为它是这道题除了算法本身之外的第二个大坑。2. 暴力解法的复杂度陷阱为什么第一版代码超时先说我第一次的实现思路很简单直接读入n和p读入序列a排序a枚举最小值a[i]再从i往后找满足条件的最大的a[j]更新答案按照这个思路写的代码长这样第二版修正了int问题之后#include cstdio #include vector #include algorithm using namespace std; int main() { int n; long long p; scanf(%d %lld, n, p); vectorlong long a(n); for (int i 0; i n; i) scanf(%lld, a[i]); sort(a.begin(), a.end()); int ans 0; for (int i 0; i n; i) { for (int j i ans; j n; j) { if (a[j] a[i] * p) { if (j - i 1 ans) ans j - i 1; } else { break; } } } printf(%d\n, ans); return 0; }这段代码的逻辑本身没问题我用它去跑题目给的样例数据结果是正确的。但提交到OJ上前两个测试点能过后面的大数据测试点直接超时。原因很朴素最坏情况下这个双重循环会枚举所有n×(n-1)/2对组合在n10^5量级的时候无论怎么剪枝都跑不出时间限制。我一开始还想着用“起点向后移动时终点只往后不往前”这个性质去优化也就是当i增加时j的起点不会回退。这个思路其实就是双指针的前身但当时我的写法并没有真正抓住单调性的本质内层循环依然会重复扫描很多已经被扫过的区域所以复杂度仍然是O(n^2)级别。结论很明确这道题在n10^5的情况下必须把复杂度降到一个O(nlog n)或者O(n)的级别。暴力枚举只是用来验证思路正确的手段作为最终解法是远远不够的。3. 两种正解的实现逻辑二分法和双指针法的取舍优化方向其实已经很清晰了排序之后数组有序对于每个固定的a[i]作为最小值需要找出最大的下标j使得a[j]不超过a[i]×p。形式上这就是在一个有序数组里做“不超过某个阈值的最右插入点”查询天然适合二分法。3.1 二分法直接用upper_boundC标准库里就有现成的upper_bound可以直接用。对每个i查找的是第一个大于a[i]*p的位置然后该位置前一个元素就是我们要找的a[j]此时符合条件的元素个数就是pos - i更新答案。#include cstdio #include vector #include algorithm using namespace std; int main() { int n; long long p; scanf(%d %lld, n, p); vectorlong long a(n); for (int i 0; i n; i) scanf(%lld, a[i]); sort(a.begin(), a.end()); int ans 0; for (int i 0; i n; i) { vectorlong long::iterator it upper_bound(a.begin() i, a.end(), a[i] * p); int cnt (int)(it - a.begin()) - i; if (cnt ans) ans cnt; } printf(%d\n, ans); return 0; }这个写法的时间复杂度是O(nlog n)空间复杂度O(n)在n10^5下是完全可以接受的。代码干净利落upper_bound内部是二分查找每次查找O(log n)外层n次循环总耗时在大数据点下稳定通过。3.2 双指针法利用单调性做到O(n)如果说二分法是对每个i都做一次独立查找那双指针的聪明之处在于i和j都可以往一个方向走且j不需要回退。核心观察是排序之后如果把i从0开始往右移动也就是最小值变大那么对于新的i满足条件的最大j一定不会比上一轮的j小。因为最小值变大了限制条件M ≤ m×p实际上是放宽的m变大了m×p也变大了原来能取的数现在也一定能取。所以j可以继续从上一轮的位置往右延伸不需要从头找。#include cstdio #include vector #include algorithm using namespace std; int main() { int n; long long p; scanf(%d %lld, n, p); vectorlong long a(n); for (int i 0; i n; i) scanf(%lld, a[i]); sort(a.begin(), a.end()); int ans 0; int j 0; for (int i 0; i n; i) { while (j n a[j] a[i] * p) { j; } if (j - i ans) ans j - i; } printf(%d\n, ans); return 0; }这段代码的执行流程是j从0开始i每移动一次j只要还能继续往右走就尽量走走到不满足条件的位置停下来此时从i到j-1这一段就是当前最小值下能取到的最长序列长度为j-i。然后i向右移动一位j继续沿用之前的位置不需要重置。表面上看这个代码有一个while循环好像也是O(n^2)。但实际上j在整个算法过程中只会单调递增最多从0移动到n-1一次所以j移动的总次数是O(n)的i移动的总次数也是O(n)合起来是O(n)线性时间。用双指针还有个额外的好处如果N继续加大到10^6级别二分法O(nlog n)可能也开始吃力但双指针O(n)依然能稳定运行。虽然PAT甲级一般不会卡到这种极限程度但笔试多的大厂笔试题经常会在这种“看似能过、实则卡log”的地方做文章能写双指针就尽量写双指针。4. 实测中的数据类型翻车int乘法溢出的完整排查链这块单独拿出来写是因为它是我实际做题时最无语的一次翻车也希望读者能避开。我用二分法版本本地跑样例输出正确提交上去却出现“答案错误”而且不是小数据出错是中等规模的数据点就开始出错。当时第一反应是二分边界写错了对着upper_bound的用法检查了半天也没看出问题。后来在本地自己构造了边界数据2 1000000000 1000000000 1000000000按照题目定义m 10^9p 10^9m × p 10^18。序列里最大的数也只有10^9所以两个元素都能选答案应该是2。但我的代码在某个版本里输出的是1。原因出在把a[i]*p这个乘法的结果存进了int变量或者用int去接收upper_bound的第三个参数。10^9 × 10^9 10^18早就超出了int的范围约2.1×10^9连long long都要小心但好在long long能存到9.2×10^18足够用。这个错误在样例数据上是100%复现不出来的因为样例里的数字都很小乘法结果很小完全不会触发溢出。只有构造大规模随机数据或者专门卡数据范围的测试点才能暴露。那么正确的做法是存储序列元素的数组用long longp用long long乘法结果a[i]*p直接用long long运算不要中间转成intupper_bound的第三个参数直接传long long类型的值用long long重写之后再跑上面的边界数据输出正确变为2。提交后所有测试点通过。回头看这个坑其实非常好避免只要在写代码之前先做一次“数值范围推算”所有参与乘法的变量本身的范围最大是多少相乘之后的范围是多少超出int没有超出long long没有这一步是所有算法题编码前都应该做的例行检查但确实是很多人的习惯盲区。5. 多步推导的复盘最优解思路是怎么一步步逼出来的做题复盘的时候我喜欢把思考过程重走一遍。这不仅是加深印象更重要的是能总结出一套“以后遇到类似题怎么想”的思维路径。第一步从题目定义出发明确要找的是一段“满足最大值与最小值比例约束”的元素子集且不要求连续。这一步直接决定了排序是否可行是整道题的题眼。第二步排序之后问题变成在有序数组中对每个位置i找最右边的j使a[j] ≤ a[i]×p。这个表述把一个序列问题转化成了查询问题。第三步分析查询的复杂度需求。n10^5决定了不可能对每个i都线性往后扫于是想到了二分查找。因为数组有序二分是自然的O(log n)查找方式。到这里O(nlog n)的解法已经很成熟了。第四步观察单调性看能不能去掉log。当i增大时a[i]×p增大最右边界j也单调不减。这是典型的双指针/滑动窗口使用条件于是写出O(n)版本。这套从“排序可行性”到“查询问题”再到“单调性优化”的分析链远远比单纯记住这题的解法更有价值。它适用于一大类涉及序列子集选择的问题比如接雨水、最长无重复子串、和不超过K的最长子数组等等本质上都是在找某种单调性然后利用双指针压缩遍历空间。6. 代码细节的进一步优化与变式思考这个题虽然主要解法已经确定但还有几个相关细节值得展开。6.1 用lower_bound的变式如果不想用upper_bound来查询也可以换一种写法对每个j作为最大值找第一个满足a[j] ≤ a[i]×p的i的最小值此时序列长度也是j-i1。这种反向思路不一定更优但有助于加深理解。核心逻辑是同一个不等式只是固定变量不同。6.2 重复元素多的情况序列中可能出现大量重复数字题目没有禁止。排序后重复元素会连续排列双指针法天然能处理这种情况while循环遇到相同值也能正常推进不会有问题。有一点值得注意如果序列的所有元素都相等那么答案就是n因为任意两个数都满足M ≤ m×p在p大于等于1时。双指针法在这个case下一次O(n)就能找出答案。6.3 中间值使用long long的另一种写法也有一种写法是提前把a[i]限制成double然后在比较时使用double类型做除法避免乘法溢出while (j n a[j] * 1.0 a[i] * p) { ... }这种浮点写法在系数比较极端时存在精度风险比如a[j]和a[i]*p非常接近时double的表示误差可能导致多算一个数或者少算一个数。笔试环境里这种误差往往极其难排查所以我个人建议不要用浮点数去做这种整数范围判断老老实实开long long用整数乘法既精确又高效。还有一个很多人没注意的小细节输出答案时用printf(“%d\n”, ans)变量ans本身不会超过nint够用。但如果你不小心用了long long的变量格式串也要改成%lld否则打印出来是错的。这种小问题在考场上碰到最浪费时间的不是修代码而是发现不了问题在哪。7. 从PAT甲级到笔试场景这题模式为什么这么常见刷多了PAT甲级和各大厂笔试之后会发现Perfect Sequence这种题型的套路被反复借鉴。它体现的是算法题里最经典的一套组合拳先排序降低问题维度然后用双指针或二分法扫描再考察数据类型的边界感知能力。举几个同类的经典题LeetCode 611. Valid Triangle Number给定数组统计能组成三角形的三元组个数。做法也是排序后双指针只是固定的是最大值而不是最小值。LeetCode 15. 3Sum三数之和为0排序双指针同样依赖有序数组的单调性。POJ 3061 Subsequence找最短连续子数组使和≥S滑动窗口思路和双指针完全一致。它们在数据结构层面几乎都是数组排序在算法层面都依赖双指针或二分法的单调性分析在易错点层面都包含数值范围或边界下标处理的坑。Pattern这么统一没什么特别深奥的原因因为这些题考察的是数据结构和算法里最高频、最基础的思维模式出题人希望确认考生是不是真正掌握了这种思维模式本身而不是记了几道题的固定解法。对于备考PAT甲级的同学我的建议是这道题不要只做一遍就翻篇。把它当成一个模板题分别用二分法和双指针法各写一遍代码然后再尝试修改成“找最短序列”“找有多少个完美序列”的变式。只有把这种基础Pattern内化成条件反射考场上的45分钟才不会浪费在“想思路调bug”上。8. 我在实际提交中的时间分布和优化记录最后分享一组我当时做题的实测数据给一个直观体感。我用的测试环境是一台普通的笔记本编译器是gOJ平台的判定时间限制是200ms不同年份可能略有不同。以下是在自己的机器上跑同一组随机数据n100000数据范围1~10^9的耗时数据版本核心算法是否通过暴力双层循环int乘法O(n^2)不通过大数据点超时二分法upper_boundlong longO(nlog n)通过耗时约30ms双指针单调扫描long longO(n)通过耗时约12ms这个数据可以清楚地看到在普通数据量下二分法和双指针差距并不悬殊但双指针的实现思想和扩展性明显更好。同时强烈建议在本地验证时要专门构造两类边界测试数据。第一类是数据范围顶格的全边界数据比如n100000所有数都取10^9验证溢出问题。第二类是极端重复数据比如序列里全是1。这两类数据测试通过后代码在上OJ时被边界测试点卡住的概率就小很多了。写到这里这道题该说的基本都说完了最后再分享一个小技巧如果将来你在笔试或OJ上遇到“某个测试点答案错误”“本地结果全对提交却不对”的诡异情况优先怀疑的就是数据类型边界然后是下标访问越界最后才去翻算法逻辑。按照这个顺序排查比漫无目的地反复读代码高效得多。