[백준-4307]-[그리디알고리즘]-개미

문제링크 : https://www.acmicpc.net/problem/4307

이문제는 그림으로 보면서 풀면 이해가 제일 쉬울거 같다.

길이 10의 막대기가 있고 개미 3마리가 있다.

개미들의 위치는 2, 6, 7에 있다.

	개미1				개미2	개미3
1 (지나면 끝)	2	3	4	5	6	7	8	9	10  (닿으면 끝)

여기서 무시해야될 조건이 있다.

두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

위의 조건은 무시하고 각 개미가 떨어지는 시간의 최소와 최대를 구해보면

	최소	최대
개미1	2	8
개미2	4	6
개미3	3	7

각 개미의 최소 시간중 제일 큰 값은 4, 최대 시간의 제일 큰 값은 8  주어진 예제의 원하는 값과 같다.

각 개미들이 만나는 상황은 신경 쓸 이유가 없다는 뜻이다. 

즉 이문제를 푸는 방법은 각 개미가 떨어지는데 걸리는 최소값과 최대값으로 출력하고자 하는 모든 개미가 떨어지는 최소 최대 시간을 구할 수 있다.

소스

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B_4307 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int testCnt = Integer.parseInt(st.nextToken());
        
        for(int i=0; i < testCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int length = Integer.parseInt(st.nextToken());
            int antCnt = Integer.parseInt(st.nextToken());
            
            int ants[] = new int[antCnt];
            
            int min = Integer.MIN_VALUE;
            int max = Integer.MIN_VALUE;
            
            for(int j=0; j < antCnt; j++) {
                st = new StringTokenizer(br.readLine());
                int ant = Integer.parseInt(st.nextToken());
                
                int antMin = Math.min(ant, length-ant);
                int antMax = Math.max(ant, length-ant);
                
                min = Math.max(min, antMin);
                max = Math.max(max, antMax);
            }
            System.out.println(min + " " + max);
        }
    }
}