java 带详细思路 | 题解 | #坠落的蚂蚁#

/*
 * 我们只关心蚂蚁A，碰撞可以分两种情况讨论：
 * 1.蚂蚁A不参与的碰撞，即蚂蚁A左右两边的蚂蚁的碰撞，只是交换了速度
 * 	碰撞后还是两个粒子，向不同方向运动，碰撞发生与否，对蚂蚁A没有影响
 * 
 *  即：蚂蚁A不参与的碰撞可以看作：没有碰撞！！
 *  
 * 2.蚂蚁A参与的碰撞，分几种情况讨论
 *  	2.1碰撞时刻，只有两只蚂蚁：
 *  
 *  		B-->...A...    ==>    ...(BA)...   ==>   ...A->...    
 *  
 *  		即蚂蚁B与蚂蚁A的碰撞，就是将蚂蚁B的速度给蚂蚁A
 *  		可以看作：蚂蚁A此时遵循蚂蚁B的运动轨迹
 *  		
 *  	2.2多画几只蚂蚁
 *  
 *  		B-->...A.......<--C.......<--D
 *  
 *  		蚂蚁A先遵循蚂蚁B的运动轨迹，遇到蚂蚁C后停止，遇到蚂蚁D后，遵循蚂蚁D的运动轨迹
 *  		如果只有这几只蚂蚁，则蚂蚁A最后掉落的时间，与蚂蚁D不发生碰撞的掉落时间一致
 *  		
 *  	2.3再多几只蚂蚁
 *  
 *  		N只蚂蚁-->......蚂蚁A......<--N只蚂蚁....蚂蚁D....<--K只蚂蚁蚂蚁
 *  
 *  		蚂蚁A最终，遵循蚂蚁D的轨迹		
 *  
 *  	
 *  	
 *  
 *  	2.4对于三只蚂蚁的碰撞：蚂蚁A没动，会遵循下一次碰撞蚂蚁的运行轨迹，合并到了2.3里
 *  	
 *  
 *  综上：
 *  	找到2.3中的蚂蚁D
 *  	或者蚂蚁A左右两侧，朝向蚂蚁A运动的蚂蚁，的数目相等，蚂蚁A不会掉落
 *  	
 *  		
 * 	
 * 
 */
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		//接收输入，顺便标记蚂蚁A
		Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int tagA=0;//用于标记蚂蚁A
        int[] location=new int[n];
        int[] speed = new int [n];
        for(int i=0;i<n;i++) {
        	location[i]=sc.nextInt();
        	speed[i]=sc.nextInt();
        	if(speed[i]==0) {
        		tagA=i;
        	}
        }
        
        //统计A两侧，朝向A运动的蚂蚁的数目,并将所有蚂蚁的位置记录在find[]中
        int leftNum=0;
        int rightNum=0;
        int[] find=new int [100];
        for(int i=0;i<n;i++) {
        	if(location[i]<location[tagA]&&speed[i]>0) {
        		find[location[i]]++;
        		leftNum++;
        	}
        	if(location[i]>location[tagA]&&speed[i]<0) {
        		find[location[i]]++;
        		rightNum++;
        	}
        }
        
        //比较两侧蚂蚁数目的大小
        if(leftNum==rightNum) {
        	System.out.println("Cannot fall!");
        }else if(leftNum<rightNum) {
        	int sum=0;
        	for(int i=location[tagA]+1;i<100;i++) {       		
        		sum+=find[i];
        		if(sum==leftNum+1) {
        			System.out.println(i);//这里的i表示蚂蚁A最终遵循的蚂蚁的位置，向左运动，也等于掉落时间
        			return;
        		}
        	}
        }else  {
        	int sum=0;
        	for(int i=location[tagA]-1;i>=1;i--) {//注意i的初始值是A的位置-1
        		sum+=find[i];
        		if(sum==rightNum+1) {
        			System.out.println(99-i+1);//这里的是向右运动，时间计算不一样
        			return;
        		}
        	}
        	
        }
        
	}
}