admin 管理员组

文章数量: 1086866

C. Robot Collisions(思维)

题目链接
outputstandard output
There are n robots driving along an OX axis. There are also two walls: one is at coordinate 0 and one is at coordinate m.

The i-th robot starts at an integer coordinate xi (0<xi<m) and moves either left (towards the 0) or right with the speed of 1 unit per second. No two robots start at the same coordinate.

Whenever a robot reaches a wall, it turns around instantly and continues his ride in the opposite direction with the same speed.

Whenever several robots meet at the same integer coordinate, they collide and explode into dust. Once a robot has exploded, it doesn’t collide with any other robot. Note that if several robots meet at a non-integer coordinate, nothing happens.

For each robot find out if it ever explodes and print the time of explosion if it happens and −1 otherwise.

Input
The first line contains a single integer t (1≤t≤1000) — the number of testcases.

Then the descriptions of t testcases follow.

The first line of each testcase contains two integers n and m (1≤n≤3⋅105; 2≤m≤108) — the number of robots and the coordinate of the right wall.

The second line of each testcase contains n integers x1,x2,…,xn (0<xi<m) — the starting coordinates of the robots.

The third line of each testcase contains n space-separated characters ‘L’ or ‘R’ — the starting directions of the robots (‘L’ stands for left and ‘R’ stands for right).

All coordinates xi in the testcase are distinct.

The sum of n over all testcases doesn’t exceed 3⋅105.

Output
For each testcase print n integers — for the i-th robot output the time it explodes at if it does and −1 otherwise.

Example
inputCopy
5
7 12
1 2 3 4 9 10 11
R R L L R R R
2 10
1 6
R R
2 10
1 3
L L
1 10
5
R
7 8
6 1 7 2 3 5 4
R L R L L L L
outputCopy
1 1 1 1 2 -1 2
-1 -1
2 2
-1
-1 2 7 3 2 7 3
Note
Here is the picture for the seconds 0,1,2 and 3 of the first testcase:

Notice that robots 2 and 3 don’t collide because they meet at the same point 2.5, which is not integer.

After second 3 robot 6 just drive infinitely because there’s no robot to collide with.

分析：

在0-m的数轴上，有n个机器人，每个机器人初始在坐标xi上（各不相同），向左或向右移动，花费一秒移动1。若遇到0或m，则改变方向。如果机器人同时移动到同一个整数位置，那么这些机器人就会爆炸。求每个机器人爆炸的时间，如果不会爆炸，就输出-1.
发现只有初始坐标同为奇数或者同为偶数的机器人才会相撞，所以根据机器人初始坐标的奇偶分别处理。
两个机器人相撞，一个机器人p初始位置为x1，方向为d1，另一个机器人q初始位置为x2，方向为d2（x1<x2）
（1）d1是向右，d2是向左：（x2-x1）/2

（2）d1是向右，d2是向右，那么q遇到m后改变方向与p相撞：m-x2+(m-(x1+m-x2)/2),化简得：（2*m-x1-x2）/2

（3）d1是向左，d2是向左，那么p遇到0后改变方向与q相撞：x1+（x2-x1）/2化简得：(x2+x1)/2

（4）d1是向左，d2是向右：m-x2+(m-(m-x2-x1)/2),化简得：（2*m+x1-x2）/2

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int N = 3e5+10;
struct node
{int x,d,t;
}e[N];
int l[N],a[N],n,m;
bool cmp(int x,int y)
{return e[x].x<e[y].x;
}
void ff(int z)
{int p=0,t;for(int i=1;i<=n;i++){t=l[i];if(e[t].x%2==z){if(e[t].d==1||!p){a[++p]=t;}else{e[t].t=e[a[p]].t=(e[t].x-e[a[p]].x*e[a[p]].d)/2;p--;}}}for(;p>1;p=p-2){e[a[p]].t=e[a[p-1]].t=(2*m-e[a[p]].x-e[a[p-1]].x*e[a[p-1]].d)/2;}if(p)e[a[p]].t=-1;
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&e[i].x);l[i]=i;}char s;for(int i=1;i<=n;i++){cin>>s;e[i].d=s=='R'?1:-1;}sort(l+1,l+1+n,cmp);ff(0),ff(1);for(int i=1;i<=n;i++){printf("%d ",e[i].t);}printf("\n");}return 0;
}

本文标签： C Robot Collisions(思维)

版权声明：本文标题：C. Robot Collisions(思维) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1698394491a297749.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。