题解 | #坠落的蚂蚁#

#include <iostream>
using namespace std;

int ant[200];

int main() {
    int n; //蚂蚁的个数
    while (scanf("%d", &n) != EOF) { // 注意 while 处理多个 case
        int position, direction;
        int posOfA;
        for (int i = 0; i < 100; i++) {
            ant[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &position, &direction);
            ant[position] = direction;
            if (direction == 0) { //记录下A的位置
                posOfA = position;
            }
        }
        //统计A左边向右走的蚂蚁数l,和右边向左走的蚂蚁数r
        int l = 0, r = 0;
        for (int i = 0; i < posOfA; i++) {
            if (ant[i] > 0) {
                l++;
            }
        }

        for (int i = posOfA; i < 100; i++) {
            if (ant[i] < 0) {
                r++;
            }
        }

        if (l == r) {
            printf("Cannot fall!\n");
        } else if (l > r) {
            int count = r;
            int i;
            for (i = posOfA; i >= 0, count >= 0; i--) {
                if (ant[i] > 0) {
                    count--;
                }
            }
            printf("%d\n", 100 - i - 1);
        } else { //l < r
            int count = l;
            int i;
            for (i = posOfA; i < 100, count >= 0; i++) {
                if (ant[i] < 0) {
                    count--;
                }
            }
            printf("%d\n", i - 1);
        }

    }
}
// 64 位输出请用 printf("%lld")

首先想一个问题。如果两只蚂蚁相碰，从微观上看，他们交换速度；但从宏观上看，还是可以看成两只蚂蚁按原速度行驶。所以在蚂蚁A左侧，且向左走的蚂蚁，不管和别的蚂蚁怎么相遇，最后都会掉下去，（可能是别的蚂蚁与他交换速度，替他掉了下去），同理，在蚂蚁A右侧，且向右走的蚂蚁，最后也会掉下去·，这两种情况的蚂蚁可以忽略，宏观上不会对A产生影响。

步骤

1、对蚂蚁位置进行排序

2、找到原来静止的蚂蚁A

3、统计A左边向右走的蚂蚁数l,和右边向左走的蚂蚁数r

4、如果l=r，两边的蚂蚁相互抵消，最终蚂蚁A静止，掉不下去

5、如果l>r，左边r个蚂蚁和右边r个抵消，（从中间一对一对的抵消）最后左边第 l-r 个蚂蚁把速度传给了A，下标为l-r-1(从0开始）A向右走，直到掉下去

6、如果l<r，左边l个蚂蚁和右边l个抵消，（从中间一对一对的抵消）最后右边第r-l个蚂蚁把速度传给了A，下标为2*l(从0开始）A向左走，直到掉下去

————————————————

原文链接：https://blog.csdn.net/han_hhh/article/details/105547426