CF1525C Robot Collisions(模拟+思維)

題目傳送門

題意

就是給你一堆機器人，第一行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;
	}
}