C++ 1236 区块合并 自己测试数据正确但测试点错误

Question

题目：
http://ybt.ssoier.cn:8088/problem_show.php?pid=1236
1236 区间合并

代码：

#include<bits/stdc++.h>
using namespace std;
struct S
{
    int begin,end;
}l,ll;
bool cmp(S a,S b)
{
    if(a.begin!=b.begin) return a.begin >b.begin;
    else return a.end>b.end;
}
struct stack
{
    S data[10001];
    int len;
    void In(S x)
    {
        len++;
        data[len]=x;
    }
    S Out()
    {
        len--;
        return data[len+1];
    }
}X;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>l.begin>>l.end;
        X.In(l);
    }
    sort(X.data+1,X.data+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        l=X.Out();
        if(X.len==0)
        {
            cout<<l.begin<<" "<<l.end;
        }
        else
        {
            ll=X.Out();
            if(l.end>=ll.begin)
            {
                l.end=ll.end;
                X.In(l);
            }
            else
            {
                cout<<"no";
                return 0;
            }
        }
    }
}

问题：
我觉得写的没问题，自己也是有测试过数据的
但是过不了

请不要直接发答案，而是给出修改建议，可以的话请上面程序批注错误

Answer 1

思路复杂了，先确定x，再确定y。
首先stack有点多余了，数组就能读写了，这里stack意义不大，还影响了你的思路。
排序的方向有问题，不应该从大到小，而是从小到大，方便你找出最小的x，剩下的就是确定y了。
写了个例子，希望能帮助你理解。

#include <algorithm>
#include <iostream>

using namespace std;

//区间定义
struct RNAGE {
    int x;
    int y;
};

bool mycmp(const RNAGE &a, const RNAGE &b) {
    if (a.x != b.x) {
        return a.x < b.x;
    }
    else {
        return a.y < b.y;
    }
}

int main() {
    /*
    input
    5
    5 6
    1 5
    10 10
    6 9
    8 10
    output
    1 10
    */


    //所有区间
    const int MAXN = 5e4 + 4;
    RNAGE data[MAXN];

    //输入区间数量
    int n;
    cin >> n;

    //输入所有区间
    int i;
    for (i = 0; i < n; i++) {
        cin >> data[i].x >> data[i].y;
    }

    //排序,排序之后最小的x就能确定了，是第一个区间的x。
    sort(data, data + n, mycmp);

    //排序之后
    /*
    1 5
    5 6
    6 9
    8 10
    10 10
    */

    //遍历
    RNAGE curr = data[0]; //假设我们要求的区间就是第一个区间，此时是[1,5]
    for (i = 1; i < n; i++) {
        if (data[i].x > curr.y) {//将我们要求区间的y与当前遍历区间的x相比，若小于则说明没有交集
            cout << "no" << endl;
            return 0;
        }
        else { //否则，我们保存比当前区间大的y.这样就找到了最大的y
            curr.y = max(curr.y, data[i].y);
        }
    }
//第一次循环：i=1,data[i]是5 6,curr.y=data[0].y=5, 5>5不成立，进入else，将curr.y更新成6
//第二次循环：i=2,data[i]是6 9,curr.y=data[1].y=6, 6>6不成立，进入else，将curr.y更新成9
//第二次循环：i=3,data[i]是8 10,curr.y=data[2].y=10, 8>9不成立，进入else，将curr.y更新成10
    cout << curr.x << " " << curr.y << endl;

    return 0;
}