uva - 10881 - Piotr's Ants（等效變換，排序）

題意：一根長為L厘米的木棍上有n只螞蟻，每只螞蟻要麼向左爬，要麼向右爬，速度為1厘米/秒，當相撞時同時掉頭（掉頭時間忽略不計），給出初始位置和朝向，計算T秒後的位置和朝向。

方法：和另一個螞蟻的題目有點像，螞蟻相撞等於對穿而過，問題在於那個螞蟻不是螞蟻了，所以問題就變為分清誰是誰的問題，詳見《算訓》P9。

注意：寫的這個程序改寫了劉大大的某些部分，例如重載了‘<'後用sort，C++已忘。。所以用了qsort。還有就是Ant｛｝的轉換，不知道為啥反正vs不行，有知道的大牛麻煩告訴，萬分感謝。

#define Local
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   

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了。