题目链接：https://codeforces.com/contest/1525/problem/C

题目描述

给你一个数n代表机器人的数量，m代表边界，n个整数代表机器人的位置，n个字符代表机器人的运动方向，
每个机器人从时间0开始运动，一个时间单位移动一单位长度，机器人碰到边界会转向，只有两个机器人在 整数坐标 相撞时才会爆炸，问这些机器人在什么时间爆炸。

思路

首先，整数点才能相撞并爆炸，说明起点在奇数的坐标只能和起点在奇数的坐标相撞，起点在偶数的坐标只能和起点为偶数的坐标相撞，也就是说坐标奇偶性不同的两个机器人不能相撞。那我们应该将坐标进行分类讨论，不要忘了先将坐标点排序。那接下来呢？因为距离近的机器人会先相撞，距离远的会后相撞，这就跟括号匹配是一样的了，用一个栈去模拟括号匹配的过程，如果有剩下的元素，那栈里剩下来的元素一定是先LLLL...RRRRR这样的组合，L向左走撞上边界转向，所以从头到尾处理每一对的L，两两相撞，距离就是(L1的坐标+L2的坐标)/2，R从尾到头，同样算出距离。最后L最多剩下一个，R也最多剩下一个，如果L和R都有剩下的，就模拟两个坐标都转向再冲向彼此，算出距离即可

本来应该用函数去写，这样简单又简洁。

code

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%d ", (x))
//#define int long long
#define endl "\n"
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-') w = -1;
    for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * w;
}
const long long N = 3e5 + 7;
struct z {
    int x;
    char c;
    int pos;
};
bool cmp(z aa, z bb) { return aa.x < bb.x; }
int t, n, len;
z a[N];
int timi[N];
z st1[N], st2[N];
int s1, s2;
int main() {
    t = read();
    while (t--) {
        mem(timi, -1);
        n = read(), len = read();
        for (int i = 1; i <= n; i++) sc(a[i]), a[i].pos = i;
        for (int i = 1; i <= n; i++) {
            scanf(" %c", &a[i].c);
        }
        sort(a + 1, a + 1 + n, cmp);
        s1 = 0, s2 = 0;
        mem(st1, 0), mem(st2, 0);
        for (int i = 1; i <= n; i++) {  //对奇数和偶数分别括号匹配
            if (a[i].x & 1) {
                if (s1 >= 1 && a[i].c == 'L' && st1[s1].c == 'R') {
                    int s = abs(st1[s1].x - a[i].x) / 2;
                    timi[st1[s1].pos] = s;
                    timi[a[i].pos] = s;
                    s1--;
                } else
                    st1[++s1] = {a[i].x, a[i].c, a[i].pos};
            } else {
                if (s2 >= 1 && a[i].c == 'L' && st2[s2].c == 'R') {
                    int s = abs(st2[s2].x - a[i].x) / 2;
                    timi[st2[s2].pos] = s;
                    timi[a[i].pos] = s;
                    s2--;
                } else
                    st2[++s2] = {a[i].x, a[i].c, a[i].pos};
            }
        }
        //奇数：
        int sum1 = 0;
        for (int i = 2; i <= s1; i += 2) {  //处理多余的‘L’
            if (st1[i].c == 'R') {
                sum1 = i - 1;
                break;
            }
            int s = (st1[i].x + st1[i - 1].x) / 2;
            timi[st1[i].pos] = s;
            timi[st1[i - 1].pos] = s;
        }
        if (st1[sum1].c == 'R') sum1--;
        for (int i = s1; i >= 2; i -= 2) {  //处理多余的‘R’
            if (st1[i - 1].c == 'L') break;
            int s = (2 * len - (st1[i].x + st1[i - 1].x)) / 2;
            timi[st1[i].pos] = s;
            timi[st1[i - 1].pos] = s;
        }
        if (sum1 % 2 == 1 &&
            (s1 - sum1) % 2 ==
                1) {  //如果处理完还剩下一个L和R则两个分别掉头相撞
            int s = (2 * len + st1[sum1].x - st1[sum1 + 1].x) / 2;
            timi[st1[sum1].pos] = s;
            timi[st1[sum1 + 1].pos] = s;
        }
        //偶数：
        sum1 = 0;
        for (int i = 2; i <= s2; i += 2) {
            if (st2[i].c == 'R') {
                sum1 = i - 1;
                break;
            }
            int s = (st2[i].x + st2[i - 1].x) / 2;
            timi[st2[i].pos] = s;
            timi[st2[i - 1].pos] = s;
        }
        if (st2[sum1].c == 'R') sum1--;
        for (int i = s2; i >= 2; i -= 2) {
            if (st2[i - 1].c == 'L') break;
            int s = (2 * len - (st2[i].x + st2[i - 1].x)) / 2;
            timi[st2[i].pos] = s;
            timi[st2[i - 1].pos] = s;
        }
        if (sum1 % 2 == 1 && (s2 - sum1) % 2 == 1) {
            int s = (2 * len + st2[sum1].x - st2[sum1 + 1].x) / 2;
            timi[st2[sum1].pos] = s;
            timi[st2[sum1 + 1].pos] = s;
        }
        for (int i = 1; i <= n; i++) pr(timi[i]);
        printf("\n");
    }
}