Falling ants (Peking University entrance exam questions)

1：题目

一根长度为 1 米的木棒上有若干只蚂蚁在爬动.

它们的速度为每秒一厘米或静止不动,方向只有两种,向左或者向右.

如果两只蚂蚁碰头,则它们立即交换速度并继续爬动.

三只蚂蚁碰头,则两边的蚂蚁交换速度,中间的蚂蚁仍然静止.

如果它们爬到了木棒的边缘（0 或 100 厘米处）则会从木棒上坠落下去.

在某一时刻蚂蚁的位置各不相同且均在整数厘米处（即 1,2,3,…99 厘米）,有且只有一只蚂蚁 A 速度为 0,其他蚂蚁均在向左或向右爬动.

给出该时刻木棒上的所有蚂蚁位置和初始速度,找出蚂蚁 A 从此时刻到坠落所需要的时间.

输入格式
第一行包含一个整数表示蚂蚁的个数 N,之后共有 N 行,每一行描述一只蚂蚁的初始状态.

每个初始状态由两个整数组成,中间用空格隔开,第一个数字表示初始位置厘米数 P,第二个数字表示初始方向,−1 表示向左,1 表示向右,0 表示静止.

输出格式
蚂蚁 A 从开始到坠落的时间.若不会坠落,输出 Cannot fall!.

数据范围
2≤N≤99,
1≤P≤99
输入样例：
4
10 1
90 0
95 -1
98 -1
输出样例：
98
难度：中等
时/空限制：1s / 64MB
总通过数：279
总尝试数：638
来源：北京大学考研机试题
算法标签

2：代码实现

#include <bits/stdc++.h>
#define vi vector<int>
#define vp vector<pair<int, int>>
using namespace std;
int A;

int main() {
    
    int n; cin >> n;
    vi l, r;
    vp data;
    while(n --)
    {
    
        int a, b; cin >> a >> b;
        if(b == 0) A = a;
        else data.push_back({
    a, b});
    }
    sort(data.begin(), data.end());
    for(auto i : data)
    {
    
        if(i.first < A && i.second == 1) l.push_back(i.first);
        else if(i.first > A && i.second == -1) r.push_back(i.first);
    }

    if(l.size() == r.size()) cout << "Cannot fall!";
    else if(l.size() > r.size()) cout << 100 - l[l.size()-r.size()-1];
    else cout << r[l.size()];

    return 0;
}