如何优化C++大输入代码性能？附航班调度代码提速需求

• 关闭标准流同步：添加ios_base::sync_with_stdio(false); cin.tie(nullptr);代码，解除C与C++标准输入流的同步绑定，避免额外IO同步开销，显著提升cin读取速度。
• 使用高效输入函数：针对大量整数或简单字符串输入，直接用C语言的scanf，或基于getchar实现自定义快速输入函数，比默认cin更快。
• 减少不必要拷贝：函数参数优先用const T&引用传递，避免大型对象拷贝；容器操作优先用emplace系列方法（如emplace_back）代替push_back，减少临时对象创建。
• 预分配容器内存：对vector、string等容器，提前调用reserve()分配足够内存，避免动态扩容时的内存拷贝与重新分配开销。
• 批量读取数据：一次性将大块数据读入内存缓冲区，再从缓冲区解析内容，减少系统IO调用次数，降低IO延迟。
• 禁用IO流异常：通过cin.exceptions(ios::failbit);关闭不必要的异常抛出，减少异常处理带来的性能损耗。

原代码性能瓶颈分析 #

原代码的MaximumNumberOfPlanes方法遍历每个航班的到达时间，再调用NumberOfPlanes遍历所有航班判断重叠情况，时间复杂度为O(n²)。当航班数量达到万级甚至十万级时，嵌套遍历会导致运行时间急剧增加，无法高效处理大规模数据。

优化方案：扫描线算法 #

将所有航班的到达、离开时间转化为事件，排序后遍历统计当前同时停靠的航班数，即可得到最大重叠数（即所需最少登机口数量），时间复杂度优化为O(n log n)（主要开销来自事件排序）。

优化后的代码 #

#include <vector>
#include <algorithm>

struct Airplane {
    int arrival_time_seconds;
    int departure_time_seconds;
};

class Schedule {
private:
    const std::vector<Airplane> airplanes_;

public:
    Schedule(const std::vector<Airplane>& airplanes) : airplanes_(airplanes) {}

    int MaximumNumberOfPlanes() const {
        std::vector<std::pair<int, int>> events;
        events.reserve(airplanes_.size() * 2); // 预分配内存，避免多次扩容

        for (const auto& plane : airplanes_) {
            // 到达事件：当前航班开始停靠，计数+1
            events.emplace_back(plane.arrival_time_seconds, 1);
            // 离开事件：当前航班完全离开，计数-1（偏移1秒，确保departure_time_seconds时刻仍被统计）
            events.emplace_back(plane.departure_time_seconds + 1, -1);
        }

        // 排序规则：先按时间升序；时间相同时，先处理离开事件，避免同一时间点的到达/离开错误叠加计数
        std::sort(events.begin(), events.end(), [](const auto& a, const auto& b) {
            if (a.first != b.first) {
                return a.first < b.first;
            }
            return a.second < b.second;
        });

        int current_planes = 0;
        int max_planes = 0;
        for (const auto& event : events) {
            current_planes += event.second;
            if (current_planes > max_planes) {
                max_planes = current_planes;
            }
        }

        return max_planes;
    }
};

优化点说明 #

1. 时间复杂度优化：从O(n²)降至O(n log n)，可轻松处理十万级甚至百万级的航班数据。
2. 内存预分配：提前为事件容器分配足够空间，避免动态扩容带来的内存拷贝开销。
3. 事件排序逻辑：确保同一时间点的离开事件先处理，保证统计结果准确（避免将同一时间离开和到达的航班误判为同时停靠）。
4. 单次遍历统计：仅需遍历一次排序后的事件列表即可得到结果，减少不必要的循环次数。

内容的提问来源于stack exchange，提问作者SK_33