[第五届蓝桥杯省赛C++A/B组]蚂蚁感冒

来源： 第五届蓝桥杯省赛C++A/B组

算法标签：数学

题目描述

长 100 厘米的细长直杆子上有 n 只蚂蚁。

它们的头有的朝左，有的朝右。

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

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

这些蚂蚁中，有 1 只蚂蚁感冒了。

并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。

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

输入格式

第一行输入一个整数 n, 表示蚂蚁的总数。

接着的一行是 n 个用空格分开的整数 Xi, Xi 的绝对值表示蚂蚁离开杆子左边端点的距离。

正值表示头朝右，负值表示头朝左，数据中不会出现 0 值，也不会出现两只蚂蚁占用同一位置。

其中，第一个数据代表的蚂蚁感冒了。

输出格式

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

数据范围

1<n<50,
0<|Xi|<100

输入样例1：

3
5 -2 8

输出样例1：

1

输入样例2：

5
-10 8 -20 12 25

输出样例2：

3

思路

依据下图分析：

1.有蚂蚁N个，母体一个，最重要的关系就是速度恒等，也就是方向相同，后者追不上前者。
2.将双方撞上，题目中的逻辑是掉头返回，但也可以视作做无体积碰撞前进，
3.在母体右边且往左走的蚂蚁与在母体左边且往右走的蚂蚁必定被感染

为什么这么想？（无体积碰撞前进）
因为在速度恒等，与母体为坐标中心的设定下，排除母体的两端蚂蚁相撞之后，与原有路线数量完全一致。

C++ 代码

#include<iostream>

using namespace std;

const int N=1e5+10;
int l,r,a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<=n;i++)
        {
            cin>>a[i];
            if(i)//0作为基准，1再判断，能省一点是一点
                if(a[i]>0&&abs(a[i])<abs(a[0]))l++;//当前蚂蚁向左走，蚂蚁自身在母体蚂蚁右边，必然被感染
                else if(a[i]<0&&abs(a[i])>abs(a[0]))r++;//蚂蚁向右走 蚂蚁自身在母体蚂蚁左边，必然被感染  
        }
        
    if(a[0]<0&&!l||a[0]>0&&!r)cout<<1;//如果所有蚂蚁都保持一个方向，就输出母体一个
    else cout<<l+r+1;
    return 0;
}