题解 | 坠落的蚂蚁

#include <stdio.h>
#include <vector>
#include <algorithm>
//有且只有一只蚂蚁A速度为0，
// 算法核心逻辑:
// 1. 左边向右的蚂蚁和右边向左的蚂蚁会相遇并交换速度
// 2. 每次相遇都会"抵消"一对蚂蚁对静止蚂蚁A的影响
// 3. 最终影响蚂蚁A运动方向的将是未抵消的蚂蚁
using namespace std;
// 定义蚂蚁结构体，包含位置和速度
typedef struct Ant {
    int pos;
    int dir;
};
// 比较函数，用于按位置排序
bool cmp(const Ant& a, const Ant& b) {
    return a.pos < b.pos;// 按pos升序排序
}
int main() {
    int n;
    scanf("%d", &n);
    vector<Ant> ant(n);
    vector<Ant>::iterator it;
    int s = -1;//静止蚂蚁A的ant动态数组索引
    // 读入所有蚂蚁数据
    int i = 0;
    for (it = ant.begin(); it != ant.end(); it++) {
        int a, b;
        scanf("%d %d", &a, &b);
        it->pos = a;
        it->dir = b;
        if (ant[i].dir == 0) { //更新静止蚂蚁A的位置
            s = i;
        }
        i++;
    }
    // 如果没有静止的蚂蚁（静止蚂蚁的位置没有更新），则输出Cannot fall!
    if (s == -1) {
        printf("Cannot fall!\n");
        return 0;
    }
    // 创建两个数组存储符合条件的蚂蚁
    int vl_count = 0, vr_count = 0;
    //统计蚂蚁A两边的蚂蚁数量
    for (i = 0 ; i < n; i++) {
        if (ant[i].pos < ant[s].pos &&
                ant[i].dir > 0) { //统计蚂蚁A左边向右的蚂蚁的数量
            vl_count++;
        } else if (ant[i].pos > ant[s].pos &&
                   ant[i].dir < 0) { //统计蚂蚁A右边向左的蚂蚁的数量
            vr_count++;
        }
    }
    vector<Ant> ant1(vl_count); // 存储左边向右的蚂蚁的位置和速度
    vector<Ant> ant2(vr_count); // 存储右边向左的蚂蚁的位置和速度
    int vl_count1 = 0;
    int vr_count1 = 0;
    for (i = 0 ; i < n; i++) {
        if (i == s) {
            continue; // 跳过静止蚂蚁
        }
        if (ant[i].pos < ant[s].pos &&
                ant[i].dir > 0) { //统计蚂蚁A左边向右的蚂蚁的位置和速度
            ant1[vl_count1].pos = ant[i].pos;
            ant1[vl_count1].dir = ant[i].dir;
            vl_count1++;
        } else if (ant[i].pos > ant[s].pos &&
                   ant[i].dir < 0) { //统计蚂蚁A右边向左的蚂蚁的位置和速度
            ant2[vr_count1].pos = ant[i].pos;
            ant2[vr_count1].dir = ant[i].dir;
            vr_count1++;
        }
    }
    // 对两个数组按位置排序
    //左边向右的蚂蚁按位置升序排列(从远到近)
    sort(ant1.begin(), ant1.end(), cmp);
    //右边向左的蚂蚁按位置升序排列(从近到远)
    sort(ant2.begin(), ant2.end(), cmp);
    // 根据算法判断结果
    if (vl_count1 ==
            vr_count1) { //蚂蚁A左边向右的蚂蚁的数量等于右边向左的蚂蚁
        printf("Cannot fall!\n");
    } else if (vl_count1 >
               vr_count1) {//蚂蚁A左边向右的蚂蚁的数量大于右边向左的蚂蚁
        // 蚂蚁A最终向右坠落，需要找到第(vl_count - vr_count)只蚂蚁
        int index = vl_count1 - vr_count1 - 1;
        printf("%d\n", 100 - ant1[index].pos);
    } else {//蚂蚁A左边向右的蚂蚁的数量小于右边向左的蚂蚁
        // 蚂蚁A最终向左坠落，需要找到第(vl_count+1)只蚂蚁
        // 注意：当vr_count > vl_count时，输出vr[vl_count].pos
        printf("%d\n", ant2[vl_count1].pos);
    }
    return 0;
}