POJ:Ants

容易想到暴力解法


最短时间；朝向都相同

最长时间、

两只蚂蚁相遇后，当他们保持原样交错而继续前进也不会有任何问题。这样看来，可以认为每只蚂蚁都是独立运动的，所以需求最长时间，只要求蚂蚁到杆子端点的最大距离就好了。

这样，无论最长时间还是最短时间，都只需要对每只蚂蚁检查一次就好了，这是O(N)时间的算法

package 程序设计竞赛;

import java.util.Scanner;

public class Ants {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int L=sc.nextInt();
		int n=sc.nextInt();
		int[] a=new int[n];
		for(int i=0;i<n;i++){
			a[i]=sc.nextInt();
		}
		//最短时间：
		int minT=0;
		//每个小蚂蚁
		for(int i=0;i<n;i++){
			//看小蚂蚁是离左边近还是右边近，之间就去大的时间
			minT=Math.max(minT,Math.min(a[i],L-a[i]));
		}
		//最长时间
		int maxT=0;
		for(int i=0;i<n;i++){
			maxT=Math.max(maxT, Math.max(a[i],L-a[i]));
		}
		System.out.println(minT);
		System.out.println(maxT);
	}

}