详细题解 | 菠萝排名问题（固定数组版）

一、代码核心构成解析

1. 结构体定义

struct str {
    int x, y, id;
}s[1000005];

• 定义了一个名为 str 的结构体，包含三个整型成员：
  • x：菠萝的甜度指标；
  • y：菠萝的酸度指标；
  • id：菠萝的编号（从1开始）。
• 同时直接声明了一个固定大小的结构体数组 s，大小为 1000005，对应题目中 n≤10⁶ 的数据范围（预留5个额外空间避免数组越界）。
• 数组 s 分配在静态存储区/栈区（注：超大数组不建议直接声明，后续会说明），用于存储所有菠萝的完整信息。

2. 自定义比较函数（排序规则）

bool cmp (str x2, str y2) {
    if (x2.x != y2.x) return x2.x > y2.x;  // 规则1：甜度降序
    if (x2.y != y2.y) return x2.y < y2.y;  // 规则2：甜度相同，酸度升序
    return x2.id < y2.id;                  // 规则3：甜、酸度相同，编号升序
}

这是 std::sort 排序的核心，用于定义两个菠萝对象的比较逻辑，严格遵循题目要求的排名优先级：

• 返回值为 true 时，表示 x2 的排名高于 y2，排序后 x2 会排在 y2 前面；
• 层层递进判断，先对比甜度，再对比酸度，最后对比编号，无冗余判断，逻辑清晰。

3. 主函数执行流程

int main () {
    int n, a, b;
    cin >> n >> a >> b;  // 读取菠萝总数n、甜度阈值a、酸度阈值b
    
    // 步骤1：读取所有菠萝数据，填充结构体数组
    for (int i = 1;i <= n;i++) {
        cin >> s[i].x >> s[i].y;  // 读取第i个菠萝的甜、酸度
        s[i].id = i;              // 给第i个菠萝分配编号（与输入顺序一致，从1开始）
    }
    
    // 步骤2：对所有菠萝按排名规则排序
    sort(s + 1,s + n + 1,cmp);
    
    // 步骤3：筛选符合条件的菠萝并输出编号
    for (int i = 1;i <= n;i++) {
        if (s[i].x >= a && s[i].y <= b) {  // 筛选条件：甜度≥a 且 酸度≤b
            cout << s[i].id << " ";
        }
    }
    return 0;
}

主函数分为3个核心步骤，流程连贯，符合问题解决的基本逻辑。

二、代码执行流程（结合样例验证）

以题目输入样例#1为例，一步步拆解执行过程：

输入样例#1

3 2 5
1 1  （第1个菠萝）
4 3  （第2个菠萝）
2 5  （第3个菠萝）

步骤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平台会忽略，但不符合严格的输出格式要求。
• 优化方案：记录符合条件的菠萝数量，遍历时分情况输出：

  int cnt = 0;  // 统计符合条件的数量
  for (int i = 1;i <= n;i++) {
      if (s[i].x >= a && s[i].y <= b) {
          if (cnt > 0) cout << " ";  // 非第一个元素，先输出空格
          cout << s[i].id;
          cnt++;
      }
  }
  

3. 次要问题2：输入输出效率不足

• 问题：当 n=10⁶ 时，cin/cout 的默认同步机制会导致输入输出速度较慢，可能出现超时。
• 优化方案：在主函数开头添加输入输出加速语句，关闭C++与C语言标准输入输出的同步：

  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  

4. 次要问题3：不必要的排序开销

• 问题：代码对所有菠萝进行了排序，包括不符合条件（x<a 或 y>b）的菠萝，这些菠萝最终不会被输出，排序它们属于无效开销，增加了运行时间。
• 优化方案：先筛选符合条件的菠萝，再对筛选结果排序（即“先筛选，后排序”），减少排序的数据量，提升效率。

五、优化后的完整代码（解决上述问题）

#include <bits/stdc++.h>
using namespace std;

// 结构体定义
struct str {
    int x, y, id;
};

// 自定义比较函数
bool cmp (str x2, str y2) {
    if (x2.x != y2.x) return x2.x > y2.x;
    if (x2.y != y2.y) return x2.y < y2.y;
    return x2.id < y2.id;
}

// 全局数组（避免栈溢出）
str s[1000005];

int main () {
    // 输入输出加速，应对大数据量
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, a, b;
    cin >> n >> a >> b;
    
    // 步骤1：填充数组
    for (int i = 1;i <= n;i++) {
        cin >> s[i].x >> s[i].y;
        s[i].id = i;
    }
    
    // 步骤2：排序所有菠萝
    sort(s + 1, s + n + 1, cmp);
    
    // 步骤3：筛选输出，避免末尾多余空格
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        if (s[i].x >= a && s[i].y <= b) {
            if (cnt > 0) cout << " ";
            cout << s[i].id;
            cnt++;
        }
    }
    
    return 0;
}

六、总结

1. 该代码的核心思路是“先排序所有数据，再筛选有效数据”，逻辑简单，能够正确解决问题；
2. 固定数组的使用是一把“双刃剑”，简化代码的同时存在栈溢出风险，超大数组建议声明为全局变量或使用动态内存；
3. 针对大数据量场景，输入输出加速、避免末尾空格、减少无效排序是提升程序效率和规范性的关键；
4. 代码的排序规则和筛选条件完全贴合题目要求，是解决该问题的有效实现方式。

柒、无注释代码：

#include <bits/stdc++.h>
using namespace std;
struct str {
    int x, y, id;
}s[1000005];
bool cmp (str x2, str y2) {
    if (x2.x != y2.x) return x2.x > y2.x;
    if (x2.y != y2.y) return x2.y < y2.y;
    return x2.id < y2.id;
}
int main () {
    int n, a, b;
    cin >> n >> a >> b;
    for (int i = 1;i <= n;i++) {
        cin >> s[i].x >> s[i].y;
        s[i].id = i;
    }
    sort(s + 1,s + n + 1,cmp);
    for (int i = 1;i <= n;i++) {
        if (s[i].x >= a && s[i].y <= b) {
            cout << s[i].id << " ";
        }
    }
    return 0;
}