【蓝桥杯】历届试题蚂蚁感冒

历届试题蚂蚁感冒

时间限制：1.0s 内存限制：256.0MB

问题描述

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

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

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

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

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

输入格式

　　第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。

　　接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。

输出格式

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

样例输入

3
5 -2 8

样例输出

样例输入

5
-10 8 -20 12 25

样例输出

Java源代码：

 1 import java.util.Scanner;
 2 
 3 public class Main {
 4 
 5     static boolean[] dir;// true: 表示方向向右 false: 向左
 6     static int[] dis;// 绝对距离
 7     static boolean[] gm;// 是否感冒
 8 
 9     public static void main(String[] args) {
10         Scanner scanner = new Scanner(System.in);
11         int n = Integer.parseInt(scanner.nextLine());
12         dir = new boolean[n];
13         dis = new int[n];
14         gm = new boolean[n];
15 
16         String[] sarr = scanner.nextLine().split("\s+");
17         if (Integer.parseInt(sarr[0]) > 0) { // 正值向右
18             dir[0] = true; // 向右
19             dis[0] = Integer.parseInt(sarr[0]); // 获取值
20             gm[0] = true; // 感冒
21         } else { // 负值向左
22             dir[0] = false; // 向左
23             dis[0] = -Integer.parseInt(sarr[0]); // 获取绝对值
24             gm[0] = true; // 感冒
25         }
26         // 计算其他蚂蚁属性
27         for (int i = 1; i < n; i++) {
28             int tmp = Integer.parseInt(sarr[i]);
29             if (tmp > 0) {
30                 dir[i] = true;
31                 dis[i] = tmp;
32             } else {
33                 dir[i] = false;
34                 dis[i] = -tmp;
35             }
36         }
37 
38         cal();
39         int count = 0;
40         for (boolean b : gm) {
41             if (b) {
42                 count++;
43             }
44         }
45 
46         System.out.print(count);
47     }
48 
49     static void cal() {
50         // 按绝对值排序
51         for (int i = 1; i < dis.length - 1; i++) {
52             for (int j = i + 1; j < dis.length; j++) {
53                 if (Math.abs(dis[i]) > Math.abs(dis[j])) {
54                     int tmp = dis[i];
55                     dis[i] = dis[j];
56                     dis[j] = tmp;
57 
58                     boolean b = dir[i];
59                     dir[i] = dir[j];
60                     dir[j] = b;
61                 }
62             }
63         }
64 
65         if (dir[0]) { // 如果第一只蚂蚁向右
66             int mark = 0;
67             for (int i = gm.length - 1; i > 0; i--) {
68                 if (dis[0] < dis[i]) { // 左端点的距离大于感冒蚂蚁
69                     if (dir[i]) {
70 
71                     } else { // 向左的被感染
72                         gm[i] = true;
73                         mark = 1; // 标记左端点的距离小于感冒蚂蚁的也将会被感染
74                     }
75                 } else {
76                     if (dir[i] && mark == 1) { // 是否向右走且右边是否有已被感染的蚂蚁（第一只蚂蚁感染其他蚂蚁后会掉头）
77                         gm[i] = true;
78                     }
79                 }
80             }
81         } else { // 第一只蚂蚁向左
82             int mark = 0;
83             for (int i = 1; i < gm.length; i++) {
84                 if (dis[0] > dis[i]) {
85                     if (!dir[i]) {
86 
87                     } else {
88                         gm[i] = true;
89                         mark = 1;
90                     }
91                 } else {
92                     if (!dir[i] && mark == 1) {
93                         gm[i] = true;
94                     }
95                 }
96             }
97         }
98     }
99 }

评测点序号	评测结果	得分	CPU使用	内存使用	下载评测数据
1	正确	25.00	156ms	23.35MB	输入输出
2	正确	25.00	218ms	23.26MB	输入输出
3	正确	25.00	187ms	22.98MB	输入输出
4	正确	25.00	234ms	23.50MB	输入输出

【蓝桥杯】历届试题 蚂蚁感冒

【蓝桥杯】历届试题蚂蚁感冒