题目描述

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

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

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

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

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

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

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

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

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

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

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

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

数据范围
1<n<50,
0<|Xi|<100

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

首先以感冒的蚂蚁为中心，碰头之后回头和不回头其实是一样的，因为两个蚂蚁同样都感冒了，所以碰头可以看作穿过。
模拟情景：首先将碰头的概念换成穿过，先将所有数字按绝对值大小排序，你会发现中心感冒蚂蚁左边只有向右走的蚂蚁有效，向左走的蚂蚁只能穿过向右的未感冒的蚂蚁直到走出范围，同样右边的蚂蚁只有向左走的有效。然后统计中心蚂蚁左边的正数和右边的负数即可，然后有一种特殊情况如果中心蚂蚁向左走，其左边没有蚂蚁向右走，或者中心蚂蚁向右走，右边没有蚂蚁向左走时，由于速度相同，除中心蚂蚁外，任何蚂蚁都不会感冒。这种情况用if判断一下即可。

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<math.h> 
using namespace std;
int main()
{
    int a[100],i,j,n,m,first,local,ans=1,sum1=0,sum2=0;
    a[100]={0};
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        first=a[0];  //记录中心蚂蚁 
    }
    for(i=0;i<n-1;i++)
        for(j=0;j<n-i-1;j++)
            if(sqrt(a[j]*a[j])>sqrt(a[j+1]*a[j+1]))  //按绝对值大小排序 
            {
                m=a[j];a[j]=a[j+1];a[j+1]=m;
            }
        //for(i=0;i<n;i++)
        //cout<<a[i]<<" ";
    for(i=0;i<n;i++)
        if(a[i]==first)
            local=i;          //找出中心蚂蚁位置 

    for(i=0;i<local;i++)
        if(a[i]>0)
        {
            sum1++;         //判断其左边是否有向右走的蚂蚁 
            ans++;
        }

    for(i=local+1;i<n;i++)
        if(a[i]<0)
        {
            sum2++;         //判断其右边是否有向左走的蚂蚁 
            ans++;
        }
    if(sum1==0||sum2==0)
        ans=1;

    cout<<ans;
    return 0;

 } 

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla