4.7 蚂蚁爬杆
4.7 蚂蚁爬杆
基本问题 : 有一根27cm的木杆，在第3cm，7cm，11cm，17cm，23cm这5个位置上各有一只蚂蚁，木杆很细不能同时通过两只蚂蚁。开始的时候，蚂蚁的头朝向是随机的，有可能朝右也有可能朝左，他们只会向前走，不会后退，当两只蚂蚁碰头时，两只蚂蚁会掉头同时朝反方向走，假设蚂蚁们每秒钟可以走1cm的距离，编写程序求出所有蚂蚁都离开木杆的最长时间与最短时间。
解法
两只蚂蚁遇见的时候同时掉头，那就可以看作是没有掉头直接穿过对方继续向前进
拓展问题
1 第i个蚂蚁，什么时候走出木杆？
解法：可以看作是每只蚂蚁背了不同重量的粮食，然后碰头之后，将粮食互换，然后掉头。假设有M只蚂蚁向左走，N只蚂蚁向右走，那么最终也将会有M只蚂蚁木杆左边落下，N只蚂蚁从木杆右侧落下.原因很简单，因为每次相遇都掉头，实质上并没有改变朝向左边或者右边的蚂蚁的数量，所以我们想要看第i只蚂蚁什么时候走出木杆，就需要先判断这只蚂蚁的朝向，如果朝向左，就看这个蚂蚁是头向左的第k只蚂蚁，然后看从左边下落第k袋粮食的时间就是蚂蚁下落的时间。
2 如果蚂蚁在一个平面上运动，同样也是碰头后原路返回（这样和弹性碰撞不同，没有相当于两个蚂蚁交换继续前进的本质），问蚂蚁如何走出平面？
解法：感觉有问题，如果蚂蚁正好构成三角形，就会死锁
3 问蚂蚁一共会碰撞多少次？
解法：每次两只蚂蚁相遇，蚂蚁就相当于穿过对方继续向前前进，古总的碰撞次数就等于每只蚂蚁穿过蚂蚁的数量。对于头朝向左的蚂蚁，只会穿过在他左边且头朝向右的蚂蚁的数量
4 两人A（速度为a），B（速度为b），在一直路上相向而行。在A，B距离s的时候，A放出一个格子C（速度为c），C飞到B之后，立即掉头飞向A，遇到A之后再飞向B。就这样在AB之间飞来飞去，直到AB相遇。问这期间鸽子一共飞了多少路程？
解法：不要考虑花里胡哨的，直接以时间为基线.
\(c*\frac{s}{a+b}\)
轮船（速度为a）在长江（速度为b）里逆流而上行驶。某一个时刻，从船上落下一个救生圈到水中，一个小时后，船员发现，掉头寻找，问经过多长时间可以找到?
解法：1个小时
// 4.7 蚂蚁爬杆
import java.util.*;
class Test{
public static void main(String[] args) {
/**
基本问题
有一根27cm的木杆，在第3cm，7cm，11cm，17cm，23cm这5个位置上各有一只蚂蚁，木杆很细
不能同时通过两只蚂蚁。开始的时候，蚂蚁的头朝向是随机的，有可能朝右也有可能朝左，他们只
会向前走，不会后退，当两只蚂蚁碰头时，两只蚂蚁会掉头同时朝反方向走，假设蚂蚁们每秒钟可以
走1cm的距离，编写程序求出所有蚂蚁都离开木杆的最长时间与最短时间。
> 解法：
两只蚂蚁遇见的时候同时掉头，那就可以看作是没有掉头直接穿过对方继续向前进
*/
/**
拓展问题
1 第i个蚂蚁，什么时候走出木杆？
解法：可以看作是每只蚂蚁背了不同重量的粮食，然后碰头之后，将粮食互换，然后掉头。
假设有M只蚂蚁向左走，N只蚂蚁向右走，那么最终也将会有M只蚂蚁木杆左边落下，N只蚂蚁从木杆右侧落下
原因很简单，因为每次相遇都掉头，实质上并没有改变朝向左边或者右边的蚂蚁的数量，所以我们想要看第i只
蚂蚁什么时候走出木杆，就需要先判断这只蚂蚁的朝向，如果朝向左，就看这个蚂蚁是头向左的第k只蚂蚁，然后看
从左边下落第k袋粮食的时间就是蚂蚁下落的时间。
2 如果蚂蚁在一个平面上运动，同样也是碰头后原路返回（这样和弹性碰撞不同，没有相当于两个蚂蚁交换继续前进的本质），问蚂蚁如何走出平面？
解法：感觉有问题，如果蚂蚁正好构成三角形，就会死锁
3 问蚂蚁一共会碰撞多少次？
解法：每次两只蚂蚁相遇，蚂蚁就相当于穿过对方继续向前前进，古总的碰撞次数就等于每只蚂蚁穿过蚂蚁的数量。
对于头朝向左的蚂蚁，只会穿过在他左边且头朝向右的蚂蚁的数量。
4 两人A（速度为a），B（速度为b），在一直路上相向而行。在A，B距离s的时候，A放出一个格子C（速度为c），C飞到B之后，立即掉头飞向A，遇到A之后再飞向B。就这样在AB之间飞来飞去，直到AB相遇。问这期间鸽子一共飞了多少路程？
解法：不要考虑花里胡哨的，直接以时间为基线，$c*\frac{s}{a+b}$
5 轮船（速度为a）在长江（速度为b）里逆流而上行驶。某一个时刻，从船上落下一个救生圈到水中，一个小时后，船员发现，掉头寻找，问经过多长时间可以找到？
解法：1个小时
*/
int[] left = new int[]{4,3};
int[] right = new int[]{0,1};
int[] res = getLastMoment(4,left,right);
print(res);
}
public static void print(int[] arr){
for(int i:arr) System.out.print(i+" ");
System.out.println();
}
/**
int n : 木杆的长度
int[] left : 头朝向左的蚂蚁的位置
int[] ritgh : 头朝向右的蚂蚁的位置
return int[slow fast]
*/
public static int[] getLastMoment(int n,int[] left,int[] right){
int slow = Integer.MAX_VALUE;
int fast = Integer.MIN_VALUE;
for(int i :left){
slow = Math.min(i,slow);
fast = Math.max(i,fast);
}
for(int i:right){
slow = Math.min(n-i,slow);
fast = Math.max(n-i,fast);
}
int[] res = new int[]{slow,fast};
return res;
}
}