UVa10881 【 Piotr's Ants】

竞赛入门经典训练指南上第九页的题目，刘汝佳上面的讲解很好很简洁

蚂蚁对对碰的问题，碰到了速度大小交换，方向都反向，与之前有一道物理题POJ3684很是类似，处理思路自然是把两只蚂蚁相碰看成是穿过对方继续运动，那么我们重点要解决的就是最后Ts后的状态下 每只蚂蚁对应 刚开始的哪只蚂蚁

我的代码和训练指南上写的比起来确实麻烦不少，我太菜，以后逐渐要学会精简代码

由于蚂蚁的相对位置是不变的，我们可以按位置排好序后一一对应上，再按id排回来，注意一一对应的时候，位置和速度都要对应

#include<map>
#include<iostream>
#include<algorithm>
#pragma warning (disable : 4996)
using namespace std;
const int maxn = 10000 + 100;

struct node {
	int loca;
	int id;
	int ve;//-1表示向左，0表示turning，1表示向右
}first[maxn],second[maxn]; //first表示开始之前的所有蚂蚁的状态存储，second表示结束之后所有蚂蚁的状态存储

bool cmp(node a, node b) {
	return a.id < b.id;//按id排序
}

bool CMP(node a, node b) {
	return a.loca < b.loca;//按位置排序
}

int main() {
	int c, kase = 0;;
	scanf("%d", &c);
	while(c--) {
		map<int, int>mp;//我用了map来判断有没有 Turning
		int n, t, l;
		scanf("%d%d%d", &l, &t, &n);
		for (int i = 0; i < n; i++) {
			char ch;
			scanf("%d %c", &first[i].loca,&ch);
			first[i].id = i;
			if (ch == 'L')
				first[i].ve = -1;
			else if (ch == 'R')
				first[i].ve = 1;	
		}
		for (int i = 0; i < n; i++) {
			second[i].loca = first[i].loca + first[i].ve*t;//计算最终位置
			second[i].ve = first[i].ve;
			mp[second[i].loca]++;
		}		
		sort(first, first + n, CMP);//先把两个状态都按位置排序
		sort(second, second + n, CMP);//按位置排序
		for (int i = 0; i < n; i++) {
			first[i].loca = second[i].loca;//一一对应
			first[i].ve = second[i].ve;//一一对应
		}
		for (int i = 0; i < n; i++) {		
			if (mp[second[i].loca] != 1) {
				first[i].ve = 0;//找出Turning
			}
		}
		sort(first, first + n, cmp);//再按id排回来
		printf("Case #%d:\n", ++kase);
		for (int i = 0; i < n; i++) {
			if (first[i].loca<0 || first[i].loca>l) {
				printf("Fell off\n");
			}
			else {
				printf("%d ", first[i].loca);
				if (!first[i].ve) {
					printf("Turning\n");
				}
				else {
					if (first[i].ve == 1) {
						printf("R\n");
					}
					else if(first[i].ve==-1){
						printf("L\n");
					}
				}
			}
		}
		printf("\n");
	}
	return 0;
}

不懂欢迎骚扰