CSP期末预测之最佳阈值：从暴力枚举到排序递推的O(n log n)优化-北京尧图网络

1. 从暴力枚举到排序递推这道题到底在考什么如果你刷过CCF-CSP的历年真题会发现一个很有意思的规律第一题通常是送分题第二题开始上强度而有些第二题看似简单实则暗藏杀机。2020年12月这场考试的第二题期末预测之最佳阈值就是一道典型的看起来能暴力实际上暴力会超时的题目。先把题意用大白话翻译一遍。假设你是某门课的助教期末考完之后你手里有一堆学生的平时表现分和是否及格的记录。现在你想定一个及格线——如果某个学生的平时分大于等于这个线你就预测他及格小于这个线你就预测他不及格。问题是这个线定在多少能让你的预测准确率最高如果多个线并列最高取最大的那个。这道题的核心矛盾在于阈值是一个连续变量但真正会改变预测结果的只有那些出现在数据里的分数值。你定一个3.5和定一个3.7如果数据里根本没有3.6这个分数那两者的预测结果完全一样。所以候选阈值只需要从已有的分数里挑。很多人第一反应是那我枚举每一个候选阈值对每个阈值再遍历一遍所有学生统计正确数取最大值不就行了这个思路没错但复杂度是O(n²)。题目里n最大能到10^5平方级别就是10^10次操作妥妥超时。所以这道题真正的考点是如何把O(n²)优化到O(n log n)。我当年第一次做这道题的时候就是老老实实写了个双重循环本地小数据跑得飞快一提交直接TLE。后来才想明白这题的优化思路和前缀和是同一个套路——排序之后利用单调性做递推。下面我把整个思考过程拆开讲包括我踩过的坑和最后总结出的模板写法。2. 暴力解法为什么一定会超时复杂度账要算清楚2.1 朴素枚举的复杂度分析先明确一下暴力解法的具体做法。假设我们有n条记录每条记录是(score, result)其中result是0或10表示不及格1表示及格。对于每一个候选阈值t从所有出现过的score里取我们遍历所有n条记录如果score t且result 1预测正确计数加一如果score t且result 0预测正确计数加一外层循环最多n次内层循环n次总操作数约n²。当n10^5时n²10^10。现代计算机每秒大概能执行10^8到10^9次简单操作10^10次至少需要10秒以上而CSP的时限通常是1秒。所以暴力必死。这里有个细节要注意候选阈值的数量其实不是n而是去重后的分数个数最多也是n。所以复杂度还是O(n²)。2.2 一个容易被忽略的边界相同分数的处理在暴力解法里还有一个坑如果多个学生有相同的分数但result不同怎么办举个例子分数都是5一个及格一个不及格。如果阈值定为5那么两个人都被预测为及格那个实际不及格的人就预测错了。如果阈值定为6两个人都被预测为不及格那个实际及格的人就错了。所以相同分数的记录在统计时不能简单去重必须全部保留。这也是为什么很多人想用去重计数来优化结果发现答案不对。去重本身没问题但去重的同时要记录每个分数对应的及格人数和不及格人数后面递推的时候要用到。提示这道题的输入里score的范围是0到10^8result只有0和1。数据规模n最大10^5。看到这个范围基本可以确定正解是O(n log n)的排序递推。3. 排序之后答案其实藏在前缀里3.1 核心洞察阈值移动时预测结果如何变化假设我们把所有记录按score从小到大排序。现在考虑阈值从某个分数移动到下一个更大的分数时预测结果会发生什么变化。设当前阈值为t所有score t的人被预测为不及格所有score t的人被预测为及格。当我们把阈值提高到tt是比t大的下一个分数那么分数在[t, t)这个区间里的人原本被预测为及格现在被预测为不及格。他们的预测结果翻转了如果这些人实际及格result1原本预测正确现在预测错误正确数减一如果这些人实际不及格result0原本预测错误现在预测正确正确数加一所以正确数的变化量该区间内不及格人数 - 该区间内及格人数。这个洞察是整道题的钥匙。有了它我们就不需要每次重新遍历所有人只需要在排序后的数组上从左到右扫一遍维护一个当前正确数然后根据每个分数区间的情况更新即可。3.2 前缀和的两种统计口径具体实现时我习惯用两个前缀数组来加速查询pre0[i]排序后前i个记录中result0的个数pre1[i]排序后前i个记录中result1的个数这样对于任意一个分数区间不及格人数就是pre0的差值及格人数就是pre1的差值。但更简洁的做法是直接计算每个候选阈值对应的正确数用一个变量滚动更新。设排序后的记录为(s[0], r[0]), (s[1], r[1]), ..., (s[n-1], r[n-1])。初始阈值设为比所有分数都小比如-1此时所有人被预测为及格。正确数所有result1的人数记为total1。然后我们从左到右遍历排序后的数组每次处理一批相同分数的记录。假设当前处理到分数为v的这一批这批里有cnt0个不及格cnt1个及格。当阈值从小于v变为等于v时这批人从预测及格变为预测不及格。正确数的变化量 cnt0 - cnt1。更新后的正确数就是阈值等于v时的正确数。我们记录这个值并和当前最优解比较。如果更优或者相等但v更大就更新答案。这里有个关键点阈值等于v时分数等于v的人被预测为及格。所以我们在处理分数v这一批时应该先计算阈值等于v的正确数然后再把这批人翻转的影响应用到下一轮。3.3 一个具体的计算例子为了让大家彻底搞明白我手算一个例子。假设有5条记录分数是否及格2031505171排序后就是上面这个顺序。total1 3三个及格。初始阈值小于2所有人预测及格正确数 3。处理分数2cnt01, cnt10。变化量 1 - 0 1。正确数变为314。阈值等于2时正确数为4。处理分数3cnt00, cnt11。变化量 0 - 1 -1。正确数变为4-13。阈值等于3时正确数为3。处理分数5cnt01, cnt11。变化量 1 - 1 0。正确数保持3。阈值等于5时正确数为3。处理分数7cnt00, cnt11。变化量 0 - 1 -1。正确数变为2。阈值等于7时正确数为2。比较所有候选阈值2时正确数4最高所以答案是2。你可以手动验证一下阈值2时预测为[及格,及格,及格,及格,及格]实际是[0,1,0,1,1]正确3个等等这里我算错了。让我重新算。阈值2分数2的人预测及格所有人分数都2所以全部预测及格。实际及格3人正确3人。但上面递推得到4说明我的递推逻辑有问题。问题出在初始状态。初始阈值小于2时所有人预测及格正确数3。处理分数2时这批人从预测及格变为预测不及格。分数2的人实际不及格原本预测及格是错的现在预测不及格是对的所以正确数应该1。变化量 cnt0 - cnt1 1 - 0 1。正确数变为4。但阈值等于2时分数2的人应该被预测为及格而不是不及格所以我在处理分数2时应该先记录阈值等于2的正确数此时分数2的人还是预测及格正确数还是3。然后才应用翻转得到阈值大于2的正确数4。所以正确的顺序是初始正确数 3阈值小于2对于分数2先记录阈值等于2的正确数 3。然后翻转正确数 cnt0 - cnt1 31 4。对于分数3先记录阈值等于3的正确数 4。然后翻转正确数 0-1 3。对于分数5先记录阈值等于5的正确数 3。然后翻转正确数 1-1 3。对于分数7先记录阈值等于7的正确数 3。然后翻转正确数 0-1 2。这样阈值2时正确数3阈值3时4阈值5时3阈值7时3。最大值是4对应阈值3。手动验证阈值3时分数3的人预测及格即3,5,5,7预测及格实际是1,0,1,1正确3个还是不对。我再仔细想想。阈值3时分数2 3预测不及格实际0正确分数3 3预测及格实际1正确分数5 3预测及格实际0错误分数5 3预测及格实际1正确分数7 3预测及格实际1正确正确4个。所以阈值3时正确数是4和递推一致。那阈值2时分数2 2预测及格实际0错误分数3 2预测及格实际1正确分数5 2预测及格实际0错误分数5 2预测及格实际1正确分数7 2预测及格实际1正确正确3个。递推得到3一致。所以我的递推逻辑修正后是正确的。关键就是先记录当前阈值的正确数再应用翻转。4. 代码实现从思路到可提交的完整版本4.1 数据结构的选择这道题的数据量是10^5用Python的话要注意常数。我推荐用列表存储排序用内置的sort然后一次线性扫描。不要用字典去重后再排序那样反而慢。具体来说把所有记录存成(score, result)的元组列表然后按score排序。排序后相同score的记录会相邻方便批量处理。4.2 核心代码逐段拆解n int(input()) records [] for _ in range(n): s, r map(int, input().split()) records.append((s, r)) # 按分数排序 records.sort(keylambda x: x[0]) # 初始正确数阈值小于所有分数所有人预测及格 total1 sum(r for _, r in records) current_correct total1 best_correct -1 best_threshold -1 i 0 while i n: # 找到当前分数的区间 j i while j n and records[j][0] records[i][0]: j 1 # 先记录阈值等于records[i][0]时的正确数 if current_correct best_correct or (current_correct best_correct and records[i][0] best_threshold): best_correct current_correct best_threshold records[i][0] # 统计这个分数区间内的0和1 cnt0 0 cnt1 0 for k in range(i, j): if records[k][1] 0: cnt0 1 else: cnt1 1 # 应用翻转阈值提高到下一个分数 current_correct cnt0 - cnt1 i j print(best_threshold)这段代码的时间复杂度是O(n log n)主要花在排序上。后面的扫描是O(n)。空间复杂度O(n)。4.3 几个容易写错的细节第一个细节是更新答案的时机。必须在处理当前分数区间之前更新因为阈值等于当前分数时这批人还是预测及格。如果你先翻转再更新就会漏掉阈值等于当前分数的情况。第二个细节是并列最优取最大阈值。题目明确说了如果多个阈值并列取最大的。所以比较的时候要用而不是或者在相等时判断阈值大小。我上面的代码用的是current_correct best_correct or (current_correct best_correct and records[i][0] best_threshold)这样能保证取到最大的。第三个细节是初始值的设置。best_correct初始为-1best_threshold初始为-1这样第一个候选阈值一定能更新。但要注意如果所有分数都是0阈值0也是合法的所以初始值不能是0。第四个细节是输入读取的效率。Python的input()在10^5数据量下可能会慢建议用sys.stdin.read().split()一次性读取。这个技巧在CSP里很实用能省不少时间。import sys data sys.stdin.read().split() n int(data[0]) records [] idx 1 for _ in range(n): s int(data[idx]) r int(data[idx1]) records.append((s, r)) idx 25. 从这道题能学到什么一类题的通用套路5.1 排序递推的适用场景这道题的核心套路是当候选答案的取值空间很大但真正影响结果的只有数据中出现的值时排序后利用相邻状态的变化量来递推。类似的题目在CSP里出现过好几次。比如区间选点类问题、中位数类问题都可以用这个思路。关键是要找到状态变化量的表达式然后从左到右扫一遍。我总结了一个判断标准如果暴力枚举每个候选值然后重新计算答案的复杂度是O(n²)而候选值之间的变化只影响局部数据那就可以考虑排序递推。5.2 前缀和与差分的思想这道题其实也可以用前缀和来写。排序后预处理pre0[i]和pre1[i]然后对于每个候选阈值正确数 pre0[小于阈值的部分] (pre1[大于等于阈值的部分])。这样每个候选阈值O(1)查询总复杂度也是O(n log n)。但滚动变量的写法更省空间也更简洁。两种写法我都试过滚动变量版本代码更短不容易出错。5.3 一个常见的思维误区很多人看到最佳阈值这四个字第一反应是二分答案。但这道题不满足二分性质——正确数随阈值的变化不是单调的。你可能会发现阈值增大时正确数先增后减但中间可能有波动。所以二分是行不通的。这也是为什么我强调要理解变化量的推导。只有理解了每个分数区间对正确数的影响才能写出正确的递推。6. 实测中的性能表现与优化建议6.1 Python版本的实测数据我用随机生成的10^5条数据测试过上面的代码在普通笔记本上运行时间大约0.3到0.5秒完全能过CSP的1秒时限。如果用sys.stdin.read()读取输入还能再快0.1秒左右。如果用PyPy提交速度会更快基本在0.2秒以内。所以Python选手不用担心这道题的性能问题关键是算法要对。6.2 常见TLE原因排查如果你提交后TLE了大概率是以下几个原因用了双重循环复杂度O(n²)排序时用了自定义比较函数Python的sort对key函数优化更好尽量用key输入读取用了input()逐行读10^5行会慢在循环里做了不必要的列表切片或字典操作提示CSP的Python环境通常是CPython不是PyPy。所以能优化的地方尽量优化比如用sys.stdin.read()、用局部变量缓存常用函数等。6.3 内存使用的注意事项10^5个元组的列表内存占用大约几MB完全没问题。但如果你用了二维数组或者字典嵌套可能会超内存。这道题的内存限制通常是256MB正常写法不会超。7. 我踩过的三个坑和对应的解决方案7.1 坑一相同分数的处理顺序我第一次写的时候把相同分数的记录分开处理了结果阈值等于某个分数时部分同分记录被翻转了部分没有导致答案错误。后来改成批量处理相同分数先记录再翻转才正确。这个坑的本质是阈值是一个大于等于的判断同分记录必须被视为一个整体。你不能把同分记录拆开否则阈值等于该分数时预测结果就不一致了。7.2 坑二并列最优的取舍题目要求并列时取最大阈值。我一开始用了更新结果取到了最小阈值。后来改成严格大于或者相等时比较阈值大小才符合要求。这个细节在CSP里很常见很多题目都有类似的并列取最大/最小的要求。读题的时候一定要圈出来。7.3 坑三初始状态的设定初始阈值应该小于所有分数此时所有人预测及格。正确数就是所有result1的人数。这个初始状态对应的是阈值小于最小分数的情况不是任何实际候选阈值。所以我们在扫描时第一个候选阈值是排序后的第一个分数此时要先记录再翻转。如果你把初始状态直接当成第一个候选阈值就会漏掉第一个分数的正确情况。8. 从这道题延伸出的练习建议如果你想巩固这类题的解法我建议按以下顺序练习先做几道纯前缀和的题熟悉预处理O(1)查询的套路再做几道排序后递推的题体会状态变化量的推导最后做这道题把两者结合起来CSP的历年真题里2019年3月的第二题、2020年9月的第二题都有类似的思路。做完这几道你对排序递推的理解会上一个台阶。另外我建议在本地写一个暴力版本和一个优化版本用随机数据对拍。这样能快速发现边界条件的错误。对拍是竞赛编程里最实用的调试技巧没有之一。最后分享一个我个人的习惯每做完一道题把核心思路用一两句话写在注释里。比如这道题我会写排序后按分数区间递推正确数变化量cnt0-cnt1先记录再翻转。这样以后复习的时候看一眼注释就能回忆起解法不用重新推导。这个习惯坚持下来你的题解库会越来越厚遇到同类题的反应速度也会越来越快。

CSP期末预测之最佳阈值：从暴力枚举到排序递推的O(n log n)优化

相关推荐

从TiDB 5.0看分布式数据库演进：HTAP、云原生与智能化运维

基于FOMIAUKF与分数阶模型的锂电池SOC估计研究与Matlab实现

直播CDN分发架构设计（进阶篇）最佳实践与踩坑记录

更多资讯

LangChain入门实战：从环境配置到对话模型调用全解析

感知算力博弈 | 纯视觉 VS 激光雷达融合谁更消耗算力，受融合架构、数据预处理、模型规模、时空对齐共同约束，理清车端真实算力开销误区

场景文本识别新范式：ResNet与Transformer的深度协同设计

Spring Boot+Vue选课系统实战：从数据库设计到并发控制全解析

系统级MCP从入门到实战：让AI直接操作硬件设备

CSS图片文字对齐不靠玄学：从基线到flex的完整方案

今日更新

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？