uva - 10881 - Piotr's Ants（等效变换，排序）

题意：一根长为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么向左爬，要么向右爬，速度为1厘米/秒，当相撞时同时掉头（掉头时间忽略不计），给出初始位置和朝向，计算T秒后的位置和朝向。

方法：和另一个蚂蚁的题目有点像，蚂蚁相撞等于对穿而过，问题在于那个蚂蚁不是蚂蚁了，所以问题就变为分清谁是谁的问题，详见《算训》P9。

注意：写的这个程序改写了刘大大的某些部分，例如重载了‘<‘后用sort，C++已忘。。所以用了qsort。还有就是Ant｛｝的转换，不知道为啥反正vs不行，有知道的大牛麻烦告诉，万分感谢。

#define Local
#include <iostream>  
#include <iomanip>  
#include <string>  
#include <cstring>  
#include <cstdio>  
#include <queue>  
#include <stack>  
#include <algorithm>  
#include <cmath>  

using namespace std;

#define MAX 10000 + 10

struct Ant
{
	int id;
	int pos;
	int dir;
}before[MAX], after[MAX];

const char dirName[][10] = {"L", "Turning", "R"};

int order[MAX];

int cmp(const void *a, const void *b)
{
	return (*(Ant *)a).pos - (*(Ant *)b).pos;
}

int main() 
{
#ifdef Local    
	freopen("a.in", "r", stdin);    
#endif
	int t = 0, i = 0, j = 0, kase = 0;
	cin >> t;
	for (kase = 1; kase <= t; kase ++)
	{
		cout << "Case #" << kase << ":" << endl;
		int L = 0, T = 0, n = 0;
		cin >> L >> T >> n;
		for (j = 0; j < n; j++)
		{
			int pos = 0, dir = 0;
			char c;
			cin >> pos >> c;
			dir = (c == ‘L‘ ? -1 : 1);
			before[j].dir = dir, before[j].pos = pos, before[j].id = j;
			after[j].dir = dir, after[j].pos = pos + T*dir, after[j].id = 0;
		}

		//计算order数组
		qsort(before, n, sizeof(before[0]), cmp);
		for (i = 0; i < n; i++)
			order[before[i].id] = i;//多理解

		//计算终态
		qsort(after, n, sizeof(after[0]), cmp);
		for (i = 0; i < n-1; i++)
			if (after[i].pos == after[i+1].pos) after[i].dir = after[i+1].dir = 0;

		//输出
		for (i = 0; i < n; i++)
		{
			int a = order[i];
			if (after[a].pos < 0 || after[a].pos > L) 
				cout << "Fell off" << endl;
			else
				cout << after[a].pos  << " " << dirName[after[a].dir+1] << endl;
		}
		cout << endl;
	}
}

一道例题错3遍你敢信？！输出那一块a写成i了。

uva - 10881 - Piotr's Ants（等效变换，排序）

原文：http://blog.csdn.net/u013545222/article/details/19154753