Educational Codeforces Round 109 C. Robot Collisions（栈的应用）

传送门
简单分析发现，如果两个机器人距离为2的整数倍，则二者不论方向如何一定会发生碰撞（先不考虑消除），转化为分别考虑坐标为奇数和坐标为偶数的机器人，（后面的思路都是按照其中一种说的）。
考虑时间，（我直接从全体上想，没有收获），查看官方题解后，思路是，对于每一个机器人来说，如果方向向左,则一定会与前面第一个方向向右的机器人相撞，创建一个栈，存放方向向右的机器人，如果栈中元素为空，则它会在x=0的墙壁反向，可以给它的坐标加一个偏移量将他的方向改为向右，存入栈中，如果该机器人方向向右，直接存入栈中，最后栈中会剩下一堆方向向右的机器人，在x=m的墙壁发生碰撞后，两两抵消，最后只剩下0，或1个不用考虑。
如果还不清楚可以看看官方题解

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 3e5+10;
struct node{
	int x,d,id,time;
}rob[N];
int n,m;
int ans[N];

bool cmp(node a,node b){
	return a.x<b.x;
}

void solve(vector<int> &s){
	while(s.size()){
		int fir = s.back();
		s.pop_back();
		if(!s.size()) break;
		int sec = s.back();
		s.pop_back();
		rob[fir].time = rob[sec].time = m-rob[fir].x+(rob[fir].x-rob[sec].x)/2;
	}
}

int main()
{
	int T;cin>>T;
	while(T--){
		vector<int>s[2];	//模拟栈，存放方向向右的机器人,分别考虑坐标为奇数和偶数的机器人
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)	scanf("%d",&rob[i].x);
		for(int i=1;i<=n;i++){
			char c;scanf(" %c",&c);
			rob[i].d = (c=='L'?-1:1);
			rob[i].id = i;
			rob[i].time = -1;
		}
		sort(rob+1,rob+1+n,cmp);
		for(int i=1;i<=n;i++){
			int st = rob[i].x%2;
			if(rob[i].d==-1){	//如果机器人方向向左，查看当前栈中有没有元素； 
				if(s[st].size()){	//如果当前栈中有元素，则该机器人和栈顶机器人碰撞，弹出栈顶元素 
					int p = s[st].back();
					s[st].pop_back();
					rob[i].time = rob[p].time = (rob[i].x-rob[p].x)/2;
				} 
				else{	//如果没有元素,将该机器人的下标加上一个偏移量，将方向改成向右存入栈中 
					rob[i].x *= -1;
					s[st].push_back(i);  
				}	
			}
			
			else{	//如过当前机器人方向向右存入栈中 
				s[st].push_back(i) ;
			}
		}
		//剩余栈中元素为方向向右的机器人，遇到第二个墙壁后，当前栈顶元素与第二个元素抵消，直到只剩下1个，或0个
		solve(s[0]);
		solve(s[1]); 
		
		for(int i=1;i<=n;i++){
			int x = rob[i].id;
			ans[x] = rob[i].time;
		}
		
		for(int i=1;i<=n;i++) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72