请你给我写个线段合并的代码模版,用cpp写。

创建于:2025年4月12日

使用 O3 Mini High 回答 Chat01

问题

请你给我写个线段合并的代码模版,用cpp写。

思考

Creating code template

The user asked for a C++ code template for merging segments, written in Chinese. This seems to be about merging overlapping intervals. My plan is to write a C++ code that reads n intervals, merges the overlapping ones, and outputs the result.

I'll make sure to include comments in Chinese, explaining the logic clearly. I’ll use STL effectively in the code to handle the intervals.

Let's get started on producing the template with detailed explanations in Chinese and clean code.

Reasoned for 8 seconds

回答

下面是一份用 C++ 实现线段合并的代码模版,此代码首先读取若干线段,然后按照区间起点排序,接着遍历线段依次进行合并,最后输出合并后的区间。请根据你的实际需要进行调整:

cpp
#include <iostream> #include <vector> #include <algorithm> struct Segment { int start, end; }; int main() { int n; std::cout << "请输入线段数量:" << std::endl; std::cin >> n; std::vector<Segment> segments(n); std::cout << "请输入每个线段的起点和终点(用空格分隔):" << std::endl; for (int i = 0; i < n; i++) { std::cin >> segments[i].start >> segments[i].end; } // 根据线段的起点进行排序,若起点相同则按照终点排序 std::sort(segments.begin(), segments.end(), [](const Segment &a, const Segment &b) { return (a.start < b.start) || (a.start == b.start && a.end < b.end); }); std::vector<Segment> merged; if (!segments.empty()) { // 将第一个线段作为初始合并区间 merged.push_back(segments[0]); // 遍历所有线段,进行合并操作 for (int i = 1; i < n; i++) { // 若当前线段的起点在已合并线段的末尾之前或正好相等,则可合并 if (segments[i].start <= merged.back().end) { // 更新当前合并线段的终点为两者终点的最大值 merged.back().end = std::max(merged.back().end, segments[i].end); } else { // 否则,将当前线段加入结果集合 merged.push_back(segments[i]); } } } // 输出合并后的线段 std::cout << "合并后的线段为:" << std::endl; for (const auto &seg : merged) { std::cout << seg.start << " " << seg.end << std::endl; } return 0; }

代码说明

  1. 结构体定义:
    定义了一个 Segment 结构体,包含 start(起点)和 end(终点)。

  2. 输入部分:
    用户首先输入线段数量,然后依次输入每个线段的起点和终点。

  3. 排序:
    使用 std::sort 按起点(若起点相同则按终点)对所有线段进行排序,为后续合并操作做准备。

  4. 合并过程:

    • 先将第一个线段加入结果集合;
    • 依次判断每一个线段的起点是否落在上一个合并线段的末尾之前。如果是,则更新合并区间的终点为两者中的较大值;
    • 否则,将当前线段加入结果集合。
  5. 输出:
    遍历 merged 容器,输出每个合并后的线段。

这份代码模版可以作为解决常见线段合并问题的基础模版,根据不同问题要求你可以进一步扩展或修改细节。

分享这个问答