坠落的蚂蚁【思维/模拟】

第一行包含一个整数表示蚂蚁的个数N（2<=N<=99），之后共有N行，每一行描述一只蚂蚁的初始状态。每个初始状态由两个整数组成，中间用空格隔开，第一个数字表示初始位置厘米数P（1<=P<=99），第二个数字表示初始方向,-1表示向左，1表示向右，0表示静止。

输出描述:

蚂蚁A从开始到坠落的时间。若不会坠落，输出“Cannot fall!”

---

思路分析

首先我们需要明确一点，$\color{red}\textbf{性质一：A蚂蚁经过偶数次碰头后速度为0}$性质一：A蚂蚁经过偶数次碰头后速度为00次碰撞时，其速度本身就为0，2次碰撞是什么情况呢？

经过两次碰撞之后，A会再次装上右侧的速度为0的蚂蚁，他的速度又回到0，永远走不出去。

---

从上面图中我们可以看到，我们只考虑了A的左侧向右走的蚂蚁，和A的右侧向左走的蚂蚁，那么还有两类左侧向左走，右侧向右走，他们对A有影响吗？

$\color{red}\textbf{性质二：左侧向左，右侧向右的蚂蚁对结果无影响}$性质二：左侧向左，右侧向右的蚂蚁对结果无影响
考虑下面左图和右图，左图中A左侧有一个向左的蚂蚁和一个向右的蚂蚁，二者相碰时则交换速度，此时对A而言，相当于右图中我们只有一个向右的蚂蚁的场景，同理，右侧向右的蚂蚁对A也是没有影响的。这也就是为什么，我们可以将蚂蚁看作可以互相穿过，而不是碰撞掉头。

---

到这里，我们已经找到了蚂蚁不能坠落的条件，也知道了影响A的个体，因此我们可以使用两个数组$l,r$l,r分别存储A的左侧向右的蚂蚁和A的右侧向左的蚂蚁，然后再来讨论他们是如何影响A的结果的（以下都假设l,r包含蚂蚁的数目各不相等），我们不妨从最简单的情况开始推导：

上面三种情况基本上包含了所有的不想等的情况，我们依次来讨论一下

1. 对于第一种情况，显然A需要的时间是$x_1$x1​。
2. 对于第二种情况，$x_2$x2​在$x_1$x1​后面，而右侧不会将A变向，所以答案仍然是$x_1$x1​。
3. 对于第三种情况，A先和$x_0$x0​碰撞，再和$x_1$x1​碰撞，此时他的速度为0，因为我们看作蚂蚁可以互相穿过所以他最后总会和$x_2$x2​碰撞，因此答案是$x_2$x2​(还是画图吧)

我们发现右侧有两个，左侧有一个的时候，决定因素在于右侧的第二个，因为左右侧相同数目的蚂蚁互相抵消，他们的碰撞使得A的速度最终为0，而打破僵局的那个蚂蚁，就是第一个左右侧数目不对等的蚂蚁。（左3右4那就是右面第四个，左3右1那就是左面第二个）

struct P {
	ll pos, v;
}a[MAX];

bool cmp(P p1, P p2) { return p1.pos < p2.pos; }

int main() {
	ll n, s;
	while (cin >> n) {
		vector<P> vl, vr;
		for (int i = 0; i < n; i++) {
			cin >> a[i].pos >> a[i].v;
			if (a[i].v == 0)s = i;
		}
		for (int i = 0; i < n; i++) {
			if (a[i].pos < a[s].pos&&a[i].v>0)vl.push_back(a[i]);
			else if (a[i].pos > a[s].pos&&a[i].v < 0)vr.push_back(a[i]);
		}
		ll l1 = vl.size(), l2 = vr.size();
		sort(vl.begin(), vl.end(), cmp); sort(vr.begin(), vr.end(), cmp);
		if (l1 == l2)printf("Cannot fall!\n");
		else if (l1 > l2) 
			cout << 100 - vl[l1 - l2 - 1].pos << endl;//99还没掉下去
		else cout << vr[l1].pos << endl;
	}
}