【程序设计竞赛】蚂蚁感冒

题目：

标题：蚂蚁感冒

    长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

资源约定：
峰值内存消耗 < 256M
CPU消耗  < 1000ms


请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

投机取巧解法：

#include <iostream>
#include<cmath>
using namespace std; 
int main()
{
    int N;
    int data[50];
    cin>>N;
    int left=0,right=0;
    //输入数据
    for(int i=0; i<N; ++i)
    {
        cin >> data[i];
    }
    for(int i=1; i<N;++i)
    {
        //找到感冒蚂蚁右边且向左走的
        if(data[i]<0&&abs(data[i])>abs(data[0]))
        {
            left++;
        }
        //找到感冒蚂蚁的左边的蚂蚁且向右走的
        if(data[i]>0&&abs(data[i])<abs(data[0]))
        {
            right++;
        }
    }
        //判断是否为特殊情况
    if((data[0]<0&&right==0)||(data[0]>0&&left==0))//第一只蚂蚁向左走，但是右面全是向左的 
    {                                               //或者第一只蚂蚁向右走，但是左面全是向右的 
        cout << "1" <<endl;
    }
    else
    {
        cout << left+right+1 << endl;
    }
    
    return 0;
}

正常解法(感谢@徐的代码提供)

#include<iostream>
#include<cmath>
using namespace std;
bool gan(int a, int b)
{
    return a + b;
}
int antnum(int *a, int *flag,int n)
{
    int count = 0;//计算感染数量
    int low=0, high=n-1;//划分区间
    while(low<high)//结束条件
    {
        while (a[low] < 0)//最左向左，最右向右，缩小空间
            low++;
        while (a[high] > 0)
            high--;
        for (int i = low; i < high; i++)
        {
            int dis = a[i] + a[i + 1];//距离(没用绝对值,绝对值发现问题就没去深入)
            if (a[i] > a[i + 1])// 1 / -5,-1/-5
            {
                if (dis < -2)
                {
                    a[i]++;
                    a[i + 1]++;
                }
                else if (dis == -2)
                {
                    if (gan(flag[i], flag[i + 1]))
                    {
                        flag[i] = flag[i + 1] = 1;
                    }
                    a[i]++;
                    a[i] = -a[i];
                    a[i + 1]++;
                    a[i + 1] = -a[i + 1];
                }
                else if (dis > -2)
                {
                    if (gan(flag[i], flag[i + 1]))
                    {
                        flag[i] = flag[i + 1] = 1;
                    }
                    a[i] = -a[i];
                    a[i + 1] = -a[i + 1];
                }
            }
            else if (a[i] < a[i + 1])//  1/5, -1/5
            {
                a[i]++;
                a[i + 1]++;
            }
        }
    }
    for (int i = 0; i < n; i++)
        if (flag[i] == 1)
            count++;
    return count;
}
int main()
{
    int n = 10;
    int *a = new int[n];
    int *flag = new int[n];
    cin >> n;
    for (int i = 0; i < n; i++)//接受数组
    {
        cin >> a[i];
        flag[i] = 0;
    }
    flag[0] = 1;
    for(int i=0;i<n-1;i++)//按绝对值冒泡排序
        for (int j = 0; j < n - i - 1; j++)
        {
            if (abs(a[j]) > abs(a[j + 1]))
            {
                int temp = a[j];//两个都交换
                a[j] = a[j + 1];
                a[j + 1] = temp;
                int temp1 = flag[j];
                flag[j] = flag[j + 1];
                flag[j + 1] = temp1;
            }
        }

    cout << antnum(a, flag, n)<<endl; 
    return 0;
}