蚂蚁(UVA 10881)

有一个长度为L的木棍,有n个蚂蚁,要么是向左爬,要么是向右爬,速度为1.两只相碰时,同时掉头.给出n个蚂蚁起始的坐标还有方向.然后再给出T秒,计算T秒后每个蚂蚁的位置 思路:两个蚂蚁相碰实际上是没有任何影响的,这等价于两者互相穿过.剩下的问题是:如何知道T秒后的蚂蚁对应原本的编号是多少. 对于最左边的第一只蚂蚁来说,若是直接朝着左边走,则对后续蚂蚁没有影响.若是朝着右边走,若下一只蚂蚁也是朝着左边走,那么两者会即将相碰. 我们知道相碰代表了互相穿过,但问题是,碰撞过后,第一只蚂蚁朝左,第二只蚂蚁变回朝右边走,两者在数轴上的相对关系并没有发生变化,第二只蚂蚁也永远不会在第一只蚂蚁的左边. 也就是说,不同编号的蚂蚁之间的相对位置是不会发生改变的.如果原本按左到右边的顺序的编号是 1 2 3 4 5 这样,那么T秒过后如果5只蚂蚁还在,那么它们的相对位置也一定是 1 2 3 4 5. 但注意,此时的编号并不是题目原本的编号,而是在一开始排序完的编号,我们用id[]来记录一开始排序完毕后的编号,此处较为繁琐… 妈的,实际写这题写的心态爆炸,调了快两小时,最后还是抄抄lrj的吧

/*
*/
#include
using namespace std;
typedef long long ll;
const int maxn = 3e5+2;
const int INF = 1e9+7;
typedef pair pii;
struct Node{
	int pos,dr,id;
	bool operator test;
	vector str;
	str.push_back("L");
	str.push_back("Turning");
	str.push_back("R");
	str.push_back("Fell off");
	int kase = 0;
	while(test--){
		int L,t,n;
		kase++;
		cin>>L>>t>>n;
		vector ord;
		for(int i=0;i>x>>ch;
			y = (ch=='R')?1:0;
			ord.push_back({x,y,i});
	}
	printf("Case #%d:\n",kase);
	 sort(ord.begin(),ord.end());
	 vector id(n+1);
	 for(int i=0;i