AtCoder 初学者竞赛 243 - C - 碰撞 2（贪婪）

题意

There are N people in an xy-plane. Person ii is at (Xi,Yi). The positions of all people are different.

We have a string S of length N consisting of L and R.
If Si​= R, Person i is facing right; if Si​= L, Person ii is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when S =(X1,Y1)=(2,3),(X2,Y2)=(1,1),(X3,Y3)=(4,1),S= RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

• 2≤N≤2×10^5
• 0≤Xi≤10^9
• 0≤Yi≤10^9
• (Xi,Yi) ≠ (Xj,Yj) if i ≠ j.
• All Xi and Yi are integers.
• S is a string of length N consisting of L and R.

输入格式

Input is given from Standard Input in the following format:

N
X1 Y1
X2 Y2
⋮
XN YN
S

输出格式

If there will be a collision, print Yes; otherwise, print No.

样例1

input
3 2 3 1 1 4 1 RRL

output
Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

样例2

input
2 1 1 2 1 RR

output
No

Since Person 1 and Person 2 walk in the same direction, they never collide.

样例3

input
10 1 3 1 4 0 0 0 2 0 4 3 1 2 4 4 2 4 4 3 3 RLRRRLRLRR

output
Yes

思路

目的是判定是否会发生碰撞。暴力枚举是O(N^2)，会TLE。正确的思路应该是：

每个点只会水平移动，要么向左，要么向右。
我们先搞清楚一个问题：什么情况下会发生碰撞？
只需符合：最左边那个人向右跑；最右边那个人向左跑。
所以我们用unordered_map，从y坐标映射到x坐标。

接下来就简单啦。先找到 准备向左跑的 站在最右边的那个人，再看看他左边存不存在准备向右跑的人，若存在，就可以双向奔赴~

代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

const int N = 1005;
int a[N], b[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> x(n), y(n);

    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    string s;
    cin >> s;

    unordered_map<int, int> dir; // 从y坐标 映射到 x坐标

    for (int i = 0; i < n; ++i)
        if (s[i] == 'L')
            dir[y[i]] = max(dir[y[i]], x[i]);

    for (int i = 0; i < n; ++i)
        if (s[i] == 'R')
            if (x[i] < dir[y[i]]) {
                cout << "Yes" << '\n';
                return 0;
            }

    cout << "No" << '\n';

    return 0;
}

原文地址：https://www.cnblogs.com/zenghaifan/p/16068177.html