题解 | #坠落的蚂蚁#

#include <algorithm>
#include <bits/stdc++.h>
#include <utility>
#include <vector>
 /*除了那个不动的蚂蚁A以外
    1.剩下的蚂蚁只有四种可能：
    1.1 在A左边，并且往左爬
    1.2 在A左边，并且往右爬
    1.3 在A右边，并且往左爬
    1.4 在A右边，并且往右爬
    2.分析如下：
    2.1 对于1和4
        这两种状态的蚂蚁对A根本没影响
    2.2 对于2和3的话
        设2的数量为left_to_right.size(),3的数量为right_to_left.size()
    2.2.1left_to_right.size()==right_to_left.size()
        我们可以抽象出一只蚂蚁 B(状态2)  和一只蚂蚁C(状态3),
    2.2.1.1如果它俩距离A相等
        毋庸置疑，属于题目中的"。三只蚂蚁碰头，则两边的蚂蚁交换速度，中间的蚂蚁仍然
        静止。"，显然A不会掉下去
    2.2.1.2如果它俩距离不等
        假设B更近，那么A先撞到B，B会变成静止，A会继承B的速度，接下来一定会遇到C，
        然后再継承C的速度，接下来又会撞到B，此时A回到了静止，综合下来结果就是，A
        不动，BC交换速度，显然A不会掉下去
    2.2.2left_to_right.size()！=right_to_left.size()
        显然左右是一对一对的抵消，最后多的那边的第一个冒出来的，它按照他原来的走法
        多久会坠落，那么A也是多久坠落*/
using namespace std;
int main() {
    int N;
    while(cin>>N)
    {
        vector<int> left_to_right;//左边向右走的蚂蚁
        vector<int> right_to_left;//右边向左走的蚂蚁
        int a,b;
        int pos=-1;//静止蚂蚁所在位置
        pair<int,int> ant;
        vector<pair<int,int>> v;
        for(int i=0;i<N;i++)
        {
            cin>>ant.first>>ant.second;
            v.push_back(ant);
        }
        sort(v.begin(), v.end(),[](const pair<int,int> & c,const pair<int,int> & d)
        {
            return c.first<d.first;
        });
        for(int i=0;i<N;i++)
        {
            a=v[i].first;
            b=v[i].second;
            if(b==0) pos=i;
            //将这个蚂蚁如果坠落，将距离压入，左边往右爬的话距离是100-a,右边往左边爬距离是a
            if(b==-1&&(i>pos&&pos!=-1))
            {
                right_to_left.push_back(a);
            }  
            if(b==1&&(i<pos||pos==-1))
            {
                left_to_right.push_back(100-a);
            }
        }
        sort(right_to_left.begin(),right_to_left.end());
        sort(left_to_right.begin(),left_to_right.end());
        //判断一下左边向右走的蚂蚁和右边向左走的蚂蚁的数量
        if(right_to_left.size()==left_to_right.size())
        {
            cout<<"Cannot fall!"<<endl;
        }
        else if(right_to_left.size()>left_to_right.size())
        {
            cout<<right_to_left[left_to_right.size()];
        }
        else cout<<left_to_right[right_to_left.size()];
    }
}
// 64 位输出请用 printf("%lld")