UVa - 10881 - Piotr's Ants

——>>汝佳新书阅读说明中的例题，大牛就是大牛！过程中两个思想：1、两只蚂蚁相撞后假设互穿而过得最终各蚂蚁位置；2、终态各蚂蚁的相对位置不变，与始态相同。
 
[cpp]  
#include <iostream>  
#include <algorithm>  
  
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 #"<<cnt++<<":"<<endl;  
        for(i = 0; i < n; i++)  
        {  
            int a = order[i];       //输入的第i只为位置上的第a只  
            if(after[a].pos < 0 || after[a].pos > L) cout<<"Fell off"<<endl;  
            else cout<<after[a].pos<<" "<<dir_name[after[a].dir+1]<<endl;  
        }  
        cout<<endl;  
    }  
    return 0;  
}

补充：软件开发 , C++ ,