北京大学复试上机 坠落的蚂蚁（牛客网）王道机试指南习题2.11

思路解析：

两个问题：

1.满足什么样的条件最初中间静止的蚂蚁不会掉下去？
2. 如果会掉下去，那么会在什么时候掉下去，数学条件是什么？

两个推论：

• 此题不考虑过程，什么时刻哪只蚂蚁具体在哪儿由哪个方向到此不作过程分析，只做宏观的状态分析，某个时刻哪个位置有一只蚂蚁：
  
• 推论一：首先确定：树枝上最初向左的蚂蚁数量和向右的蚂蚁数量在整个蚂蚁移动过程中是动态平衡的，亦即：任何时候向左（右）的蚂蚁数量都等于最初向左（右）移动的蚂蚁数量；
  • 原因：每当有两个蚂蚁碰头时，他们交换了速度，也就是交换了移动方向，也就是向左移动这个状态不过从一个蚂蚁转移到了另一个蚂蚁，另一个蚂蚁向右移动的状态转移到了前面这个蚂蚁头上，因此，在这个蚂蚁移动过程中，总的向左移动的状态数保持不变，向右移动的状态数不变；
  • 模型：把树枝拟化为数轴，另外，为了更好地考虑地状态，对于掉下去的蚂蚁，我们把树枝两端做个延展，对于到达0或100位置掉下去的蚂蚁，我们只做标记上的删除，不做实际的删除，也就是掉下去的蚂蚁还会继续沿着数轴的方向移动；
• 推论二：其次明确：假如某时某刻，左边已经掉下去了n只蚂蚁，右边掉下去了m只蚂蚁，那么我们可以确定此时左边掉下去的n只蚂蚁，一定是最初时从左边数的前n只蚂蚁，右边同理，掉下去的m只蚂蚁，一定是最初从右边数的前m只蚂蚁；

解决问题

• 什么条件下最初中间静止的蚂蚁最后不会掉下去？

  • 最后中间的蚂蚁不会掉下去，那么可假设：左边掉下去了n只蚂蚁，右边掉下去了m只蚂蚁，那么状态一定是这样的：
    

  • 由上，可见向左运动的蚂蚁有n只，向右运动的蚂蚁有m只；根据上面的推论二，从左边掉下去的n只蚂蚁，一定是最初的最左边的n只蚂蚁，右边同理；根据推论一，整个移动过程蚂蚁的移动状态动态平衡，此时如果我们把从左边掉下去的蚂蚁计作向左移动，右边掉下去的蚂蚁计作向右移动，那么根据动态平衡，可得：最初向左移动的蚂蚁是n只，最初向右移动的蚂蚁是m只；

  • 由上可得结论：如果最初向左移动的蚂蚁数量＝最初中间蚂蚁左边蚂蚁的数量，那么最后可得中间的蚂蚁一定不会调出树枝。反过来讲，如果二者不相等，那么最后左边掉出去的蚂蚁的数量并不等于所有向左移动的蚂蚁数量，这显然不符合推论一的动态平衡；

• 如果中间的蚂蚁会掉下去，会在在什么时刻，满足什么条件？假如根据上述办法已经确定中间蚂蚁一定会掉下去，首先确实初始状态下向左移动left和向右移动的蚂蚁数量right，由此确定如果所有蚂蚁掉下去，从左边掉下去的蚂蚁数量（=left）和从右边掉下去的蚂蚁数量（=right）,记最初中间蚂蚁从左边数是第xl只蚂蚁，从右边数是第xr只蚂蚁；
  • 若xl<left或xr>right，那么可以判定中间的蚂蚁是从左边掉下去的；
  • 若xl>left或xr<right，那么可以判定中间的蚂蚁是从右边掉下去的；
    假定从左边掉出去，由此，只要每一轮移动后都检查是否有蚂蚁从左边掉出去，那么从左边当掉下去的蚂蚁为xl的时刻，即是最初中间静止的蚂蚁掉下树枝需要花费的时间；

附代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef struct {
	int pos;
	int rate;
}ant_t;

bool cmp(ant_t a, ant_t b) {
	return a.pos < b.pos;
}

int main() {
	int i, N;
	ant_t ant[100];
	int moveL, moveR, left, right;//moveL/moveR表示最初方向向左（右）移动的蚂蚁数量
	//left/right表示最初静止的蚂蚁左边/右边蚂蚁数量
	while (scanf("%d", &N) != EOF) {
		moveL = moveR = 0;
		for (i = 0; i < N; i++) {
			scanf("%d %d", &ant[i].pos, &ant[i].rate);
			if (ant[i].rate == -1) {
				moveL++;
			}
			else if (ant[i].rate == 1) {
				moveR++;
			}
		}
		sort(ant, ant + N, cmp);
		left = 0;
		for (i = 0; i < N; i++) {
			if (ant[i].rate == 0) {
				break;
			}
			left++;
		}
		right = N - left - 1;
		int leftFall = 0, rightFall = 0, t = 0;
		if (left == moveL || right == moveR) {
			printf("Cannot fall!\n");
		}
		else if (left < moveL || right > moveR) {//中间的蚂蚁最终会从左边掉下树枝
			while (1) {
				for (int j = 0; j < N; j++) {
					if (ant[j].pos == 0) {
						leftFall++;
					}
					ant[j].pos += ant[j].rate;
				}
				if (leftFall == left + 1) {
					printf("%d\n", t);
					break;
				}
				t++;
			}
		}
		else if (left > moveL || right < moveR) {//中间的蚂蚁最终会从右边掉下数值
			while (1) {
				for (int j = 0; j < N; j++) {
					if (ant[j].pos == 100) {
						rightFall++;
					}
					ant[j].pos += ant[j].rate;
				}
				if (rightFall == right + 1) {
					printf("%d\n", t);
					break;
				}
				t++;
			}
		}
	}
	return 0;
}