一、代码核心构成解析
1. 结构体定义
* 定义了一个名为 str 的结构体,包含三个整型成员:
* x:菠萝的甜度指标;
* y:菠萝的酸度指标;
* id:菠萝的编号(从1开始)。
* 同时直接声明了一个固定大小的结构体数组 s,大小为 1000005,对应题目中 n≤10⁶ 的数据范围(预留5个额外空间避免数组越界)。
* 数组 s 分配在静态存储区/栈区(注:超大数组不建议直接声明,后续会说明),用于存储所有菠萝的完整信息。
2. 自定义比较函数(排序规则)
这是 std::sort 排序的核心,用于定义两个菠萝对象的比较逻辑,严格遵循题目要求的排名优先级:
* 返回值为 true 时,表示 x2 的排名高于 y2,排序后 x2 会排在 y2 前面;
* 层层递进判断,先对比甜度,再对比酸度,最后对比编号,无冗余判断,逻辑清晰。
3. 主函数执行流程
主函数分为3个核心步骤,流程连贯,符合问题解决的基本逻辑。
二、代码执行流程(结合样例验证)
以题目输入样例#1为例,一步步拆解执行过程:
输入样例#1
步骤1:填充结构体数组
循环执行 i=1,2,3,数组 s 的数据如下:
数组索引 i s[i].x(甜度) s[i].y(酸度) s[i].id(编号) 1 1 1 1 2 4 3 2 3 2 5 3
步骤2:调用 SORT 排序
排序范围是 s+1 到 s+3+1(即 s[1] 到 s[3]),使用 cmp 函数排序:
1. 对比甜度:s[2].x=4 > s[3].x=2 > s[1].x=1;
2. 无甜度相同的情况,无需对比酸度和编号;
3. 排序后数组 s 的顺序(仅关注有效数据 i=1,2,3):
数组索引 i s[i].x(甜度) s[i].y(酸度) s[i].id(编号) 1 4 3 2 2 2 5 3 3 1 1 1
步骤3:筛选并输出
遍历排序后的数组,判断 s[i].x≥2 且 s[i].y≤5:
* i=1:4≥2 且 3≤5,符合条件,输出 2 ;
* i=2:2≥2 且 5≤5,符合条件,输出 3 ;
* i=3:1<2,不符合条件,跳过;
* 最终输出结果:2 3 (末尾有一个多余空格,后续可优化)。
三、代码优点
1. 逻辑简洁直观:直接采用固定数组存储,无需手动管理动态内存(new/delete),也无需 vector 容器,代码量少,容易理解;
2. 排序高效:使用C++标准库 sort 函数(底层为快速排序优化版),时间复杂度为 O(n log n),能够应对 n≤10⁶ 的数据量;
3. 贴合题目要求:自定义比较函数严格遵循排名规则,筛选条件准确,能够得到正确结果;
4. 输入填充高效:单循环读取数据,直接填充数组,无额外数据拷贝开销。
四、代码存在的问题与优化方向
1. 核心问题:固定数组的内存风险
* 问题:s[1000005] 是超大固定大小数组,直接在函数内声明时,会被分配在栈区(栈内存大小通常有限,一般为几MB),而 1000005 个 str 结构体(每个占12字节左右)需要约12MB内存,容易导致栈溢出(Stack Overflow),程序崩溃。
* 优化方案:
1. 将数组声明为全局变量:全局变量分配在静态存储区,内存限制远大于栈区,不会溢出;
2. 改用动态数组(new 关键字):分配在堆区,内存充足,且可根据 n 灵活调整大小(避免内存浪费)。
2. 次要问题1:末尾多余空格
* 问题:输出时每个符合条件的编号后都加了空格,最终结果末尾会有一个多余空格,虽然大部分OJ平台会忽略,但不符合严格的输出格式要求。
* 优化方案:记录符合条件的菠萝数量,遍历时分情况输出:
3. 次要问题2:输入输出效率不足
* 问题:当 n=10⁶ 时,cin/cout 的默认同步机制会导致输入输出速度较慢,可能出现超时。
* 优化方案:在主函数开头添加输入输出加速语句,关闭C++与C语言标准输入输出的同步:
4. 次要问题3:不必要的排序开销
* 问题:代码对所有菠萝进行了排序,包括不符合条件(x<a 或 y>b)的菠萝,这些菠萝最终不会被输出,排序它们属于无效开销,增加了运行时间。
* 优化方案:先筛选符合条件的菠萝,再对筛选结果排序(即“先筛选,后排序”),减少排序的数据量,提升效率。
五、优化后的完整代码(解决上述问题)
六、总结
1. 该代码的核心思路是“先排序所有数据,再筛选有效数据”,逻辑简单,能够正确解决问题;
2. 固定数组的使用是一把“双刃剑”,简化代码的同时存在栈溢出风险,超大数组建议声明为全局变量或使用动态内存;
3. 针对大数据量场景,输入输出加速、避免末尾空格、减少无效排序是提升程序效率和规范性的关键;
4. 代码的排序规则和筛选条件完全贴合题目要求,是解决该问题的有效实现方式。
柒、无注释代码: