hxw的小熊猫们_牛客博客

hxw的小熊猫们

时间限制: 1 Sec 内存限制: 128 MB
</center>

题目描述

这年头，有养宠物狗的，有养宠物猫的，可hxw最近却迷上了小熊猫，于是乎，经常带着他的小熊猫们去桥边玩耍。可是由于hxw最近沉迷算法，忽略了对小熊猫们的日常呵护，导致其中一只熊猫感冒了。现在这些小熊猫都分布在桥上，有的头向左，有的头向右，每只熊猫都只能沿着桥向前爬，速度为1m/s,当两只熊猫碰面时，它们会同时掉头向前爬，同时，生病的熊猫会把感冒传染给与它碰面的那只熊猫，现在hxw想知道，当所有的熊猫全部爬离桥时，共有多少只熊猫感冒。其中桥的长度为100m。

输入

输入数据多组

每组数据第一行输入一个N(1<N<50)，表示熊猫的个数。

接着一行是N个用空格分开的整数Xi,(-100<=Xi<=100),Xi的绝对值表示熊猫离左桥头的距离，正值表示头向右，负值表示头向左，数据中不会出现0值，也不会出现两只熊猫占用同一位置，其中第一个数据代表的熊猫感冒了。

输出

要求输出一个整数，表示最后感冒熊猫的数目。

样例输入

3
5 -2 8
5
-10 8 -20 12 25

样例输出

1
3

解题思路

碰面之后掉头这个操作实际上可以忽略，效果和不掉头是一样的。假设有病的熊猫是A，A左边向右走的熊猫数量为lf，A右边向左走的熊猫数量为rg，那么:
1.A向右走，且rg==0；或者A向左走，且lf==0，ans=1；
2.ans=lf+rg+1.

具体见代码：

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int cmp(int a, int b) {
    return fabs(a) < fabs(b);
}
int main() {
    int a[50], n, m, temp, i, r, l;
    while (~scanf("%d", &n)) {
        for (i = 0; i < n; i++)
            scanf("%d", &a[i]);
        m = a[0];
        sort(a, a + n, cmp);
        temp = r = l = 0;
        for (i = 0; i < n; i++) {
            if (m == a[i]) {
                temp = 1;
                continue;
            }
            if (!temp && a[i] > 0)
                l++;
            if (temp && a[i] < 0)
                r++;
        }
        if (m > 0 && !r || m < 0 && !l) {
            puts("1");
            continue;
        }
        printf("%d\n", r + l + 1);
    }
    return 0;
}