题目传送门
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL4NGRNhXUE9EeVpHW3BjMMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL5QjM5IzN0UTM5ETNwEjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
题意
就是给你一堆机器人,第一行n代表有n个机器人,m代表坐标的范围
第二行就是每一个机器人的坐标,
第三行就是代表每一个机器人的行走属性
L代表机器人往左走,R代表机器人往右走
思路
有点太弱,调了好久。
这道题通过观察其实就可以发现,两个点同时是奇数,或者同时是偶数,才会有可能相碰。
那么我们就模拟一下。
把所有奇数的情况捡出来,排个序。
1.时间最短的情况是相遇情况。
左边是R,右边是L,这样无论如何时间都是最短的
2.时间比较短的情况是两个点方向相同
左边右边同时是L或者R,这样也可以算出来一个
3.时间最长的点是方向相反
左边是L,右边是R
因此在作答过程中,先筛出时间最短的,再筛出时间相对中等的,最后再筛出来时间相对较长的。
那么偶数的情况同理。
代码
AC代码
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
struct node{
int a;
char v;
int t;
}s[2102100];
struct tip{
int a;
char v;
int t;
}p[2102101];
int ans[2102100];
int cmp(node x,node y){
return x.a<y.a;
}
int main(){
int T;
cin>>T;
while(T--){
int n,l;
stack<int>st;
cin>>n>>l;
for(int i=1;i<=n;i++){
cin>>s[i].a;
s[i].t=i;
}
for(int i=1;i<=n;i++)scanf(" %c",&s[i].v);
sort(s+1,s+1+n,cmp);
int k=0;
for(int i=1;i<=n;i++){
if(s[i].a%2){
p[++k].a=s[i].a;
p[k].t=s[i].t;
p[k].v=s[i].v;
}
}
//cout<<k<<endl;
memset(ans,-1,sizeof ans);
for(int i=1;i<=k;i++){
// while(st.size())st.pop();
if(p[i].v=='R')st.push(i);
else {
if(st.size()){
int u=st.top();
st.pop();
ans[p[u].t]=ans[p[i].t]=abs(p[u].a-p[i].a)/2;
}
}
}
while(st.size())st.pop();
for(int i=1;i<=k;i++){
if(p[i].v=='L'&&ans[p[i].t]==-1){
//cout<<st.size()<<"\n";
if(!st.size())st.push(i);
else{
int u=st.top();
st.pop();
//cout<<st.top()<<endl;
ans[p[i].t]=ans[p[u].t]=p[u].a+abs(p[u].a-p[i].a)/2;
// cout<<p[i].t<<p[u].t<<endl;
// cout<<ans[p[i].t]<<" "<<ans[p[u].t]<<endl;
}
}
//cout<<st.size()<<endl;
}
while(st.size())st.pop();
for(int i=k;i;i--){
//stack<int>st;
//while(st.size())st.pop();
if(p[i].v=='R'&&ans[p[i].t]==-1){
if(!st.size())st.push(i);
else{
int u=st.top();
st.pop();
ans[p[i].t]=ans[p[u].t]=l-p[u].a+abs(p[u].a-p[i].a)/2;
}
}
}
queue<int>ql;
queue<int>qr;
for(int i=1;i<=k;i++) if(p[i].v=='L'&&ans[p[i].t]==-1)ql.push(i);
for(int i=k;i;i--) if(p[i].v=='R'&&ans[p[i].t]==-1)qr.push(i);
while(ql.size()&&qr.size()){
int aa=ql.front();
int bb=qr.front();
ql.pop();
qr.pop();
ans[p[aa].t]=ans[p[bb].t]=(2*l-p[bb].a+p[aa].a)/2;
}
while(ql.size())ql.pop();
while(qr.size())qr.pop();
k=0;
for(int i=1;i<=n;i++){
if(s[i].a%2==0){
p[++k].a=s[i].a;
p[k].t=s[i].t;
p[k].v=s[i].v;
}
}
while(st.size())st.pop();
for(int i=1;i<=k;i++){
if(p[i].v=='R')st.push(i);
else {
if(st.size()){
int u=st.top();
st.pop();
ans[p[u].t]=ans[p[i].t]=abs(p[u].a-p[i].a)/2;
}
}
}
while(st.size())st.pop();
for(int i=1;i<=k;i++){
if(p[i].v=='L'&&ans[p[i].t]==-1){
if(!st.size())st.push(i);
else{
int u=st.top();
st.pop();
ans[p[i].t]=ans[p[u].t]=p[u].a+abs(p[u].a-p[i].a)/2;
}
}
}
while(st.size())st.pop();
for(int i=k;i;i--){
if(p[i].v=='R'&&ans[p[i].t]==-1){
if(!st.size())st.push(i);
else{
int u=st.top();
st.pop();
ans[p[i].t]=ans[p[u].t]=l-p[u].a+abs(p[u].a-p[i].a)/2;
}
}
}
for(int i=1;i<=k;i++) if(p[i].v=='L'&&ans[p[i].t]==-1)ql.push(i);
for(int i=k;i;i--) if(p[i].v=='R'&&ans[p[i].t]==-1)qr.push(i);
while(ql.size()&&qr.size()){
int aa=ql.front();
int bb=qr.front();
ql.pop();
qr.pop();
ans[p[aa].t]=ans[p[bb].t]=(2*l-p[bb].a+p[aa].a)/2;
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
}