1 条题解

题解与来源题共享。已有题解默认通过;新增或编辑后需由来源域管理员审核。待审核、驳回题解仅作者和审核管理员可见。来源域:system

  • 2
    @ 2026-10-28 18:29:34

    看这题有点难,来写个题解玩。
    我们深度思考一下,发现:只有当两个人在同一平行线上并且相对而行时才会产生碰撞,也就是说,对于两个坐标 (x1,y1)(x_1,y_1) 和 (x2,y2) (y1<y2)(x_2,y_2)~(y_1 < y_2) ,只有当 x1=x2x_1=x_2 且第一个人方向为L,第二个人方向为R的时候,他们俩才会产生碰撞。

    暴力做法

    枚举每一对坐标,判断是否产生碰撞。
    时间复杂度:O(n2)O(n^2) 。

    优化做法

    按 xx 坐标排序并枚举每个坐标,如果 xi=xi−1x_i=x_{i-1}(在同一平行线上) 并且 si−1=s_{i-1}=R, si=s_i=L(相对而行)则产生了碰撞。
    时间复杂度:O(n)O(n) 。

    最终代码

    #include<bits/stdc++.h>
    using namespace std;
    using ll=long long;
    struct node{
        int x,y; //坐标
        char dir; //方向
    };
    bool cmp(node&a,node&b){ //自定义排序
        if(a.x==b.x) return a.y<b.y; //如果x坐标相等则按y坐标排序
        return a.x<b.x;
    }
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);cout.tie(nullptr);
        int n;
        cin>>n;
        vector<node> a(n);
        for(int i=0;i<n;i++) cin>>a[i].y>>a[i].x; //读入坐标
        for(int i=0;i<n;i++) cin>>a[i].dir; //读入方向
        sort(a.begin(),a.end(),cmp);
        for(int i=1;i<n;i++){ //枚举每对坐标
            if(a[i].x==a[i-1].x && a[i].dir=='L' && a[i-1].dir=='R'){ //判断是否产生碰撞
                cout<<"Yes";
                return 0;
            }
        }
        cout<<"No";
        return 0;
    }
    
    • 1

    信息

    ID
    127
    时间
    1000ms
    内存
    256MiB
    难度
    普及−
    标签
    递交数
    5
    已通过
    3
    上传者