两题很有趣挺经典的蚂蚁问题。

1.n只蚂蚁以1cm/s的速度在长为L的竿上爬行，当蚂蚁爬到竿子的端点就会掉落。当两只蚂蚁相撞时，只能各自反向爬回去。对于每只蚂蚁，给出距离左端的距离xi，但不知道它的朝向，求所有蚂蚁落下竿子所需要的时间的最大值和最小值。

2.问题1的升级版：把问题1改为已知每只蚂蚁的左端距离和它的朝向，要求按输入顺序输出 t 秒后每只蚂蚁的位置和状态（掉出去，转向中，或者蚂蚁的朝向）。

1.POJ 1852 Ants

思路：

很水的一题，因为以前做过问题2.so......

因为蚂蚁碰撞会反向，故我们可以直接看成是蚂蚁直接穿过去。

也就是说，这道题求解只需要独立的计算出每只蚂蚁到端点的时间即可。

最小时间只需要沿着靠近的一端走，最大时间则最远的一端。

#include
  
   
#include
   
     #include
    
      using namespace std; int a,L,n; int main() { int T; scanf(%d,&T); while(T--) { int min_ans=0,max_ans=0; scanf(%d%d,&L,&n); for(int i=0;i
     
      
 
      
 
      
2.UVA 10881 - Piotr's Ants
      
 






      
http://uva.onlinejudge.org/index.php option=com_onlinejudge&Itemid=8&page=show_problem&problem=1822
      
思路：
      
《算法竞赛入门经典-训练指南》上的题。
      
半年前被虐个半死，今天是我把他虐个半死。
      
和问题1的差别在于要求出位置。
      
那么，同样的，每只蚂蚁碰撞后反向，所以每只蚂蚁的相对顺序不变。（突然想起“不撞南墙不回头”。。。。。。。）
      
所以我们根据一开始排个序，记录此时所有蚂蚁的序号，然后计算ts后的位置。（计算我们直接加上距离，你想，0s有一只向右的位置在x的，那么ts后一只向右的位置在x+t的，不管是不是一开始向右的那只还是和他碰撞的，我们可以看为穿过去）
      
接下来再次根据位置排序，将序号进行“还原”，即对应上原来在竿上的位置。
      
最后根据序号按顺序输出即可。
      
 
      
#include
       
        
#include
        
          #include
         
           using namespace std; const int MAXN=10000+10; int L,t,n; int order[MAXN]; char string[][10]={L,R,Turning}; struct data { int id; //输入的顺序 int x; //位置 int dir; //方向 0 左 1右 2碰撞 bool operator<(const data &y)const{ return x
          
           L) //掉出去了 printf(Fell off ); else printf(%d %s ,a[i].x,string[a[i].dir]); //根据方向输出状态。 } printf( ); } return 0; }