3 条题解

  • 0
    @ 2025-12-14 12:02:07
    ```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
    上传者