链接
https://codeforces.com/contest/1525/problem/C
题意
数轴上 有 $n$ 个机器人，左端为 $0$，右端为 $m$。
每个机器人都在整数点，且不会有多个机器人在同一个整数点，每个机器人要么向左移动要么向右移动。
每个机器人的移动速度为 $1$，碰到左右两端会立即向相反方向移动。
当多个机器人在同一个整数点相撞，那么它们会爆炸。
求每个机器人是否会爆炸，会爆炸的话求出爆炸时间。
思路
首先，当两个机器人之间距离为偶数时才有可能相撞。
因为两个机器人每次移动只有四种情况：$(+1,+1)$，$(-1,-1)$，$(+1,-1)$，$(-1,+1)$。
可以发现距离奇偶性不变，这样我们可以将机器人分成奇数点和偶数点考虑。
如果没有左右端点限制，就是括号匹配问题，用栈解决。
加上端点限制。
若当前机器人向左移动，栈空时，即原始位置在当前机器人前面的机器人都会爆炸，那么当前机器人肯定会碰到左端点后向右移动，我们可以将当前机器人的原始位置 $a$ 变为 $-a$，方向变为向右，放入栈中。
最终，栈中可能会留下多个向右移动的机器人，那么这些机器人肯定会两两相撞，栈顶机器人肯定会碰到右端后向左移动与栈顶 $-1$ 位置的机器人相撞。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=3e5+5;
int stk1[N],stk2[N],res[N];
pair<pair<int,char>,int> a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;cin>>T;
while(T--) {
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) res[i]=-1;
for(int i=1;i<=n;i++) cin>>a[i].FI.FI;
for(int i=1;i<=n;i++) cin>>a[i].FI.SE;
for(int i=1;i<=n;i++) a[i].SE=i;
sort(a+1,a+1+n);
int top1=0,top2=0;
for(int i=1;i<=n;i++) {
if(a[i].FI.FI&1) {
if(a[i].FI.SE=='R') stk1[++top1]=i;
else {
if(top1>=1) res[a[i].SE]=res[a[stk1[top1]].SE]=(a[i].FI.FI-a[stk1[top1]].FI.FI)/2,--top1;
else a[i].FI.FI=-a[i].FI.FI,stk1[++top1]=i;
}
}
else {
if(a[i].FI.SE=='R') stk2[++top2]=i;
else {
if(top2>=1) res[a[i].SE]=res[a[stk2[top2]].SE]=(a[i].FI.FI-a[stk2[top2]].FI.FI)/2,--top2;
else a[i].FI.FI=-a[i].FI.FI,stk2[++top2]=i;
}
}
}
while(top1>1) res[a[stk1[top1]].SE]=res[a[stk1[top1-1]].SE]=(m-a[stk1[top1]].FI.FI+m-a[stk1[top1-1]].FI.FI)/2,top1-=2;
while(top2>1) res[a[stk2[top2]].SE]=res[a[stk2[top2-1]].SE]=(m-a[stk2[top2]].FI.FI+m-a[stk2[top2-1]].FI.FI)/2,top2-=2;
for(int i=1;i<=n;i++) {
cout<<res[i]<<" \n"[i==n];
}
}
return 0;
}
|