1 条题解
题解与来源题共享。已有题解默认通过;新增或编辑后需由来源域管理员审核。待审核、驳回题解仅作者和审核管理员可见。来源域:system
-
2
看这题有点难,来写个题解玩。
我们深度思考一下,发现:只有当两个人在同一平行线上并且相对而行时才会产生碰撞,也就是说,对于两个坐标 和 ,只有当 且第一个人方向为L,第二个人方向为R的时候,他们俩才会产生碰撞。暴力做法
枚举每一对坐标,判断是否产生碰撞。
时间复杂度: 。优化做法
按 坐标排序并枚举每个坐标,如果 (在同一平行线上) 并且
R,L(相对而行)则产生了碰撞。
时间复杂度: 。最终代码
#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
- 上传者