——>>汝佳新书
阅读说明中的例题，大牛就是大牛！过程中两个思想：1、两只蚂蚁相撞后假设互穿而过得最终各蚂蚁位置；2、终态各蚂蚁的相对位置不变，与始态相同。
?
[cpp] ?
#include ?
??
using namespace std; ?
??
const int maxn = 10000 + 10; ?
??
struct ant ? ? ?//定义蚂蚁数据类型 ?
{ ?
? ? int id; ? ? ? ? //输入时的id编号，从0开始计数 ?
? ? int pos; ? ? ? ?//距左端的位置 ?
? ? int dir; ? ? ? ?//方向 ?
? ? bool operator < (const ant &a) const ? ? ? ?//重载运算符，按位置前后为序 ?
? ? { ?
? ? ? ? return pos < a.pos; ?
? ? } ?
}; ?
ant before[maxn], after[maxn]; ? ? ?//未处理前的before，处理后为after ?
const char dir_name[][10] = {"L", "Turning", "R"}; ? ? ?//方向数组 ?
int order[maxn]; ? ? ? ?//输入的第i只蚂蚁是位置上的第order[i]只 ?
int main() ?
{ ?
? ? int N, L, T, n, i, position, change_c, cnt = 1; ?
? ? char c; ?
? ? cin>>N; ?
? ? while(N--) ?
? ? { ?
? ? ? ? cin>>L>>T>>n; ?
? ? ? ? for(i = 0; i < n; i++) ?
? ? ? ? { ?
? ? ? ? ? ? cin>>position>>c; ?
? ? ? ? ? ? if(c == 'L') change_c = -1; ? ? //转一下，等下计算终态与输出都方便 ?
? ? ? ? ? ? else change_c = 1; ?
? ? ? ? ? ? before[i] = (ant){i, position, change_c}; ?
? ? ? ? ? ? after[i] = (ant){0, position + T*change_c, change_c}; ? ? ? //计算终态，其中id无太大用处，可赋个默认值 ?
? ? ? ? } ?
? ? ? ? sort(before, before+n); ? ? //按位置排序 ?
? ? ? ? for(i = 0; i < n; i++) order[before[i].id] = i; ? ? //赋值，使输入的第i只蚂蚁是位置上的第order[i]只 ?
? ? ? ? sort(after, after+n); ? ? ? //按位置排序 ?
? ? ? ? for(i = 0; i < n-1; i++) ? ? ? ?//修改方向 ?
? ? ? ? ? ? if(after[i].pos == after[i+1].pos) ?
? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? after[i].dir = 0; ?
? ? ? ? ? ? ? ? after[i+1].dir = 0; ?
? ? ? ? ? ? } ?
? ? ? ? cout<<"Case #"<
? ? ? ? for(i = 0; i < n; i++) ?
? ? ? ? { ?
? ? ? ? ? ? int a = order[i]; ? ? ? //输入的第i只为位置上的第a只 ?
? ? ? ? ? ? if(after[a].pos < 0 || after[a].pos > L) cout<<"Fell off"<
? ? ? ? ? ? else cout<
? ? ? ? } ?
? ? ? ? cout<
? ? } ?
? ? return 0; ?
} ?
?