AcWing_1211 蚂蚁感冒(数学规律)

AcWing

1211. 蚂蚁感冒

首先，两只蚂蚁相撞掉头，可以看作时一只蚂蚁穿过了另一只蚂蚁，因为相撞之后，两只蚂蚁都正常，或者都感冒。

首先考虑一般情况，即同时存在在感染源蚂蚁右边往左走的蚂蚁和在感染源蚂蚁左边往右走的蚂蚁。感染源蚂蚁不管方向朝哪里，只要它右边的蚂蚁向左走，就会碰撞感染；同样，感染源蚂蚁左边的蚂蚁只要朝右边走，也会被感染。在这种情况下，有：ans = left + right + 1，此处，left为在感染源蚂蚁左边往右走的蚂蚁，right为在感染源蚂蚁右边往左走的蚂蚁，1为感染源蚂蚁。

特殊情况，当感染源蚂蚁向左走的时候，如果没有在感染源蚂蚁左边往右走的蚂蚁，那么感染源蚂蚁右边的蚂蚁永远不可能被感染；同理，当感染源蚂蚁向右走的时候，如果没有在感染源蚂蚁右边往左走的蚂蚁，那么感染源蚂蚁左边的蚂蚁也永远不可能被感染。在这两种情况下，感染的蚂蚁只有感染源蚂蚁一只。

#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin >> n;
    int s, l = 0, r = 0;
    cin >> s;
    while(--n){
        int a;
        cin >> a;
        if(abs(a) > abs(s) && a < 0) r++;
        if(abs(a) < abs(s) && a > 0) l++;
    }
    if((l == 0 && s < 0) || (r == 0 && s > 0)) cout << 1;
    else cout << l + r + 1;
    return 0;
}