UVa 10881 Piotr's Ants (排序)

题目意思：
算法竞赛训练指南。 9 页
1、 掉头等于 对穿而过
2、 每一只蚂蚁的相对位置都是没有改变的

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 10010;
int Test;
int L, T, N;
char direc[2] = {
    0};//表示状态int order[MaxN] = {
    0};	//输入的顺序
const char dirName[][10] = {
    "L", "Turning", "R"};struct Ant
{
    int id;int pos;int d;		//方向， -1 表示左， 0 表示 turning, 1 表示右bool operator< (const Ant & rhs) const{
    return pos < rhs.pos;}
}before[MaxN], after[MaxN];int main()
{
    scanf("%d", &Test);int p;for(int t = 1; t <= Test; ++t){
    scanf("%d%d%d", &L, &T, &N);for(int i = 0; i < N; ++i){
    scanf("%d %s", &p, direc);before[i].id = i;	//输入的下标if(direc[0] == 'R'){
    after[i].d = before[i].d = 1;}else{
    after[i].d = before[i].d = -1;	}before[i].pos = p;after[i].pos = p + T * after[i].d;}sort(before, before + N);	//按坐标排序for(int i = 0; i < N; ++i){
    order[before[i].id] = i;	// order[k] 表示第 k个输入的蚂蚁，实际的排名}sort(after, after + N);		// T 时间后，各个蚂蚁的最终排名for(int i = 0; i +	1 < N; ++i){
    if(after[i].pos == after[i + 1].pos){
    after[i].d = after[i + 1].d = 0;	//如果是 turning 的状态，修改}}printf("Case #%d:\n", t);for(int i = 0; i < N; ++i){
    int a = order[i];if(after[a].pos < 0 || after[a].pos > L){
    printf("Fell off\n");}else{
    printf("%d %s\n", after[a].pos, dirName[after[a].d + 1]);}}printf("\n");}return 0;
}/* 2 10 1 4 1 R 5 R 3 L 10 R 10 2 3 4 R 5 L 8 R *//* Case #1: 2 Turning 6 R 2 Turning Fell off Case #2: 3 L 6 R 10 R */