POJ 1852 Ants || UVA 10881 - Piotr's Ants 经典的蚂蚁问题

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

http://poj.org/problem?id=1852

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

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

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

1. int a,L,n;  
2. int main()  
3. {  
4.     int T;  
5.     scanf("%d",&T);  
6.     while(T--)  
7.     {  
8.         int min_ans=0,max_ans=0;  
9.         scanf("%d%d",&L,&n);  
10.         for(int i=0;i<n;i++)  
11.         {  
12.             scanf("%d",&a);   
13.             min_ans=max(min_ans,min(L-a,a));   //选择小的一段走  
14.             max_ans=max(max_ans,max(L-a,a));   //选择长的一段走  
15.             //因为是计算总的时间故应取最大值。  
16.         }  
17.         printf("%d %d\n",min_ans,max_ans);  
18.     }  
19.     return 0;  
20. } 

UVA 10881 - Piotr's Ants

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1822

Piotr likes playing with ants. He has n of them on a horizontal pole L cm long. Each ant is facing either left or right and walks at a constant speed of 1 cm/s. When two ants bump into each other, they both turn around (instantaneously) and start walking in opposite directions. Piotr knows where each of the ants starts and which direction it is facing and wants to calculate where the ants will end up T seconds from now.

Input
The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing 3 integers: L , T and n (0 <= n <= 10000) . The next n lines give the locations of the n ants (measured in cm from the left end of the pole) and the direction they are facing (L or R).

Output
For each test case, output one line containing “Case #x:” followed by n lines describing the locations and directions of the n ants in the same format and order as in the input. If two or more ants are at the same location, print “Turning” instead of “L” or “R” for their direction. If an ant falls off the pole beforeT seconds, print “Fell off” for that ant. Print an empty line after each test case.

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

所以我们根据一开始排个序，记录此时所有蚂蚁的序号，然后计算ts后的位置。（计算我们直接加上距离，你想，0s有一只向右的位置在x的，那么ts后一只向右的位置在x+t的，不管是不是一开始向右的那只还是和他碰撞的，我们可以看为穿过去）

接下来再次根据位置排序，将序号进行“还原”，即对应上原来在竿上的位置。

1. int L,t,n;  
2. int order[MAXN];  
3. char string[][10]={"L","R","Turning"};  
4. struct data  
5. {  
6.     int id; //输入的顺序  
7.     int x;  //位置  
8.     int dir;  //方向 0 左 1右 2碰撞  
9.     bool operator<(const data &y)const{  
10.         return x<y.x;  
11.     }  
12. }a[MAXN];  
13. bool cmp(const data& x,const data&y)  
14. {  
15.     return x.id<y.id;  
16. }  
17. int main()  
18. {  
19.     int T,kase=1;  
20.     scanf("%d",&T);  
21.     while(T--)  
22.     {  
23.         scanf("%d%d%d",&L,&t,&n);  
24.         for(int i=0;i<n;i++)  
25.         {  
26.             char dir;  
27.             scanf("%d %c",&a[i].x,&dir);   
28.             if(dir=='L') a[i].dir=0;     
29.             else    a[i].dir=1;  
30.             a[i].id=i;  
31.         }  
32.         //每只蚂蚁的相对次序是不变的，原来在左边的之后还会在左边。  
33.         sort(a,a+n);  
34.   
35.         for(int i=0;i<n;i++)  
36.         {  
37.             order[i]=a[i].id;  
38.             if(a[i].dir==0)  
39.                 a[i].x-=t;  
40.             else  
41.                 a[i].x+=t;  
42.         }  
43.         //再次排序即可由最后的位置确定对应的输入序号（相对位置不变）  
44.         sort(a,a+n);  
45.         for(int i=0;i<n-1;i++)  
46.         {  
47.             a[i].id=order[i];  
48.             if(a[i].x==a[i+1].x)  
49.                 a[i+1].dir=a[i].dir=2;  
50.         }  
51.         a[n-1].id=order[n-1];  
52.   
53.         sort(a,a+n,cmp);  //根据输入的顺序排序  
54.         printf("Case #%d:\n",kase++);  
55.         for(int i=0;i<n;i++)  
56.         {  
57.             if(a[i].x<0||a[i].x>L)     //掉出去了  
58.                 printf("Fell off\n");  
59.             else   
60.                 printf("%d %s\n",a[i].x,string[a[i].dir]);  //根据方向输出状态。  
61.         }  
62.         printf("\n");  
63.     }  
64.     return 0;  
65. } 

Read full article from POJ 1852 Ants || UVA 10881 � Piotr's Ants 经典的蚂蚁问题 | riaos