描述
一根长度为1米的木棒上有若干只蚂蚁在爬动。它们的速度为每秒一厘米或静止不动，方向只有两种，向左或者向右。如果两只蚂蚁碰头，则它们立即交换速度并继续爬动。三只蚂蚁碰头，则两边的蚂蚁交换速度，中间的蚂蚁仍然静止。如果它们爬到了木棒的边缘（0或100厘米处）则会从木棒上坠落下去。在某一时刻蚂蚁的位置各不相同且均在整数厘米处（即1，2，3，…99厘米），有且只有一只蚂蚁A速度为0，其他蚂蚁均在向左或向右爬动。给出该时刻木棒上的所有蚂蚁位置和初始速度，找出蚂蚁A从此时刻到坠落所需要的时间。
输入描述：
第一行包含一个整数表示蚂蚁的个数N（2<=N<=99），之后共有N行，每一行描述一只蚂蚁的初始状态。每个初始状态由两个整数组成，中间用空格隔开，第一个数字表示初始位置厘米数P（1<=P<=99），第二个数字表示初始方向,-1表示向左，1表示向右，0表示静止。
输出描述：
蚂蚁A从开始到坠落的时间。若不会坠落，输出“Cannot fall!”
示例1
输入：
4
10 1
90 0
95 -1
98 -1输出：
98首先，蚂蚁A可能坠落，也可能不坠落。
其中，不坠落的情况有两种，即A两边的蚂蚁，右边的蚂蚁向右边走，左边的蚂蚁向左边走，则这一类的蚂蚁都不会与A相撞；另一种情况就是存在右边的蚂蚁向左边走，左边的蚂蚁向右边走，但是，这两种蚂蚁的数量是相等的，这样也不会坠落。
而A坠落的情况，归根结底就是两种，即向右边坠落，或者向左边坠落。这里我们可以先做一下预处理，首先将蚂蚁根据其位置进行排序，对于左边的蚂蚁向左边走，右边的蚂蚁向右边走这种情况，我们可以忽略，然后左边的蚂蚁向右边走归为left数组中，右边的蚂蚁向左边走归为right数组中，left的蚂蚁有n，right的蚂蚁有m，则当n>m时，A向右边坠落，且可以简化认为A是与left中第n-m个蚂蚁（left数组从后往前数）相撞，然后开始向右边移动，并最终移动到100坠落，因此时间为100减去left中第n-m个蚂蚁的位置。当n<m时，A向左边坠落，且可以简化认为A是与right中第m-n个蚂蚁相撞，然后开始向左边移动，并最终移动到0坠落，因此时间为right中第m-n个蚂蚁的位置。
#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
struct Ant
{
int position;
int direction;
};
bool Compare(Ant x, Ant y) {
return x.position < y.position;
}
Ant ants[N];
int main() {
int n;
while (cin >> n)
{
vector<int> left, right;//分别存储0的(左侧向右的蚂蚁)和(右侧向左的蚂蚁)
int position;
for (int i = 0; i < n; ++i) {
cin >> ants[i].position >> ants[i].direction;
if (ants[i].direction == 0)
position = ants[i].position; // 不动
}
sort(ants, ants+n, Compare);//依据position升序排列
for (int i = 0; i < n; ++i) {
if (ants[i].position < position && ants[i].direction == 1)
left.push_back(ants[i].position);
if (ants[i].position > position && ants[i].direction == -1)
right.push_back(ants[i].position);
}
if (left.size() == right.size())
cout << "Cannot fall!" << endl;
else if (left.size() < right.size())
cout << right[left.size()] << endl;
else
cout << 100 - left[left.size() - right.size() - 1] << endl;
}
return 0;
}
