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;
}