LQ0212 蚂蚁感冒【序列处理】

题目来源：蓝桥杯2014初赛 C++ A组G题

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

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

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

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

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

输入描述

第一行输入一个整数 n (1

接着的一行是 n 个用空格分开的整数 Xi (−100

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

输入输出样例
示例
输入

3
5 -2 8

输出

1

问题分析
本题似乎是一个模拟题，用模拟的方法来做应该是没有问题的，但是比较复杂且慢。
本题要点整理如下：

1. 开始时，只有第一只蚂蚁感冒；
2. 蚂蚁碰头后掉头，也可以看作相互穿越；
3. 跟第一只感冒蚂蚁碰头的蚂蚁也会感冒；
4. 蚂蚁移动是有方向的；
5. 统计那些跟感冒蚂蚁相向而行的蚂蚁，它们必定跟感冒的蚂蚁碰头；
6. 跟感冒蚂蚁相向而行的蚂蚁，有可能在其左边也可能在其右边，需要看感冒蚂蚁的运动方向，也要看一般蚂蚁的运动方向。

AC的C语言程序如下：

/* LQ0212 蚂蚁感冒 */

#include 
#include 

int main()
{
    int n, a0, a;
    int l = 0, r = 0;
    scanf("%d%d", &n, &a0);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &a);
        if (a > 0 && abs(a) < abs(a0)) l++;
        if (a < 0 && abs(a) > abs(a0)) r++;
    }
    if ((a0 > 0 && r == 0) || (a0 < 0 && l == 0))
        printf("1\n");
    else
        printf("%d\n", l + 1 + r);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22