蚂蚁感冒

原创

---

问题描述

　　长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。

　　每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。

　　当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。

　　这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。

　　请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。

输入格式

　　第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。
　　接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。

　　正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。

输出格式

　　要求输出1个整数，表示最后感冒蚂蚁的数目。

样例输入

3
5 -2 8

样例输出

1

样例输入

5
-10 8 -20 12 25

样例输出

3

 

注意，用户输入的数据是乱序的，首先将用户输出的数据按绝对值大小升序排序；

题目中的前进速度1厘米/秒不必理会，蚂蚁看上去是动态的，实则可以视为静态；

离开杆子的蚂蚁是绝对不会和杆子上其他蚂蚁相撞的，其存在与否无关紧要。

只有相邻的蚂蚁才有机会相撞，并且只可能和面前的蚂蚁相撞，和其背后的蚂蚁

是不可能相撞的。所以，我们可以循环扫描蚂蚁数组，判断哪两只蚂蚁会相撞，

相撞则掉头，再在此基础上判断两只蚂蚁中是否存在只有一个蚂蚁感冒，存在则

感冒蚂蚁数+1，直到数组中所有蚂蚁都不会相撞。

 1 import java.util.*;
 2 
 3 public class 蚂蚁感冒 {
 4     static int arr[];
 5     static int flag[];    //flag[i]=1代表蚂蚁arr[i]感冒
 6     static int n=0;
 7     static int total=1;
 8     static int ff=0;    //ff==1表示蚂蚁已经不会相撞
 9     
10     /*
11      循环扫描数组，判断相邻两只蚂蚁；
12      相撞则掉头，在此基础上判断两只蚂蚁中是否存在感冒蚂蚁；
13      不相撞继续判断下一组相邻的蚂蚁；
14      直到全部蚂蚁都不会相撞。
15      */
16     
17     static void Ants() {
18         int i=0;
19         while(true) {
20             ff=1;
21             for(i=0;i<=n-1;i++) {
22                 if(i!=n-1) {
23                     if( arr[i]>0 && arr[i+1]<0 ) {
24                         ff=0;
25                         arr[i]=arr[i]*-1;
26                         arr[i+1]=arr[i+1]*-1;    //掉头
27                         if( (flag[i]==1 && flag[i+1]!=1) || (flag[i]!=1 && flag[i+1]==1) ) {    //有蚂蚁感冒
28                             total++;
29                             flag[i]=1;
30                             flag[i+1]=1;
31                         }
32                     }
33                 }
34             }
35             if(ff==1) {    //所有蚂蚁不会相撞
36                 System.out.println(total);
37                 break;
38             }
39         }
40     }
41     
42     static int YiKuan(int left,int right) {    //一趟快速排序
43         int x=0;
44         x=arr[left];
45         while(left<right) {
46             while(left<right && Math.abs(arr[right])>Math.abs(x)) {
47                 right--;
48             }
49             if(left<right) {
50                 arr[left]=arr[right];
51                 left++;
52             }
53             while(left<right && Math.abs(arr[left])<Math.abs(x)) {
54                 left++;
55             }
56             if(left<right) {
57                 arr[right]=arr[left];
58                 right--;
59             }
60         }
61         arr[left]=x;
62         return left;
63     }
64     
65     static void Quan(int left,int right) {    //快速排序
66         if(left<right) {
67             int mid=0;
68             mid=YiKuan(left,right);
69             Quan(left,mid-1);
70             Quan(mid+1,right);
71         }
72     }
73     
74     public static void main(String args[]) {
75         Scanner reader=new Scanner(System.in);
76         n=reader.nextInt();
77         arr=new int[100];
78         flag=new int[100];
79         int i=0;
80         for(i=0;i<=n-1;i++) {
81             arr[i]=reader.nextInt();
82             flag[i]=0;
83         }
84         int x=0;
85         x=arr[0];    //存储首只感冒蚂蚁的值
86         Quan(0,n-1);    //快速排序
87         for(i=0;i<=n-1;i++) {
88             if(x==arr[i]) {
89                 flag[i]=1;
90                 break;
91             }
92         }
93         
94         Ants();
95     }
96 }

(ACCEPT)

13:07:20

2018-06-14