3 条题解
-
0
```language cpp#include #include #include // 引入 INT_MAX/INT_MIN using namespace std;
// 定义区间结构 struct node { int l, r; };
// 数组大小 node a[50001];
// *** 新的比较函数:按左端点升序排序 *** bool cmp(node x, node y) { if (x.l != y.l) { return x.l < y.l; } // 左端点相同时,按右端点升序排列 return x.r < y.r; }
int main() { // 优化输入输出速度 ios::sync_with_stdio(false); cin.tie(NULL);
int n; if (!(cin >> n) || n < 1) { cout << "no" << endl; return 0; } // 1. 读取输入 (使用 1-based 索引) for (int i = 1; i <= n; i++) { cin >> a[i].l >> a[i].r; } // 2. 排序 (按左端点排序) sort(a + 1, a + 1 + n, cmp); // 3. 初始化 int current_l = a[1].l; int current_r = a[1].r; // 4. 遍历检查和合并 for (int i = 2; i <= n; i++) { // 检查当前区间 a[i] 是否与已合并区间 [current_l, current_r] 重叠或相邻 // 合并条件:a[i] 的左端点 <= 已合并区间的右端点 if (a[i].l <= current_r) { // 区间重叠或相邻,进行合并: // 更新右端点:取当前已合并区间的右端点和 a[i] 的右端点的最大值。 // 这一点是关键,因为 a[i].r 不再保证大于 current_r。 current_r = max(current_r, a[i].r); // 左端点 current_l 肯定不变,因为 a[i].l >= current_l // (因为数组按 a[i].l 排序,且 a[1].l 已经是最小的了) } else { // 发现间隙:a[i].l > current_r,无法合并 cout << "no" << endl; return 0; // 立即退出 } } // 5. 最终输出 cout << current_l << " " << current_r << endl; return 0;}
信息
- ID
- 371
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 30
- 已通过
- 4
- 上传者