[算法刷题题解笔记] 洛谷 P1007 独木桥 [贪心]

// package luogu.orange;
import java.io.*;
/**
 * ClassName: P1007
 * Package: luogu.orange
 * Description:
 *
 * @Author tcw
 * @Create 2023-06-08 20:22
 * @Version 1.0
 */
public class Main {
    // 快读快写
    private static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) {
        // 读取独木桥的长度
        int l = readInt();
        // 读取桥上士兵的个数
        int n = readInt();
        // 全部离开独木桥的最小时间，就是每个士兵都向离桥边短的方向走
        // 此时最耗时的就是最中间的那个士兵
        // 此时最短时间即最中间的那个士兵离开的时间
        // 最大时间就是每个士兵都向离桥边远的方向走
        // 此时离桥边最远的那个士兵耗费的时间就是最大时间
        // 初始化为0，没有士兵需要下，花费时间为0
        int max = 0; // 最大时间
        int min = 0; // 最小时间
        for (int i = 0; i < n; i++) {
            // 一边输入一边判断
            int location = readInt();
            // 当前士兵离开桥的两个时间，花费大的和小的
            // 桥上的坐标 1, 2, 3, ..., L
            // 士兵移动到0或L+1才算离开桥
            // 所以右边边界L还在桥上，因此l - location需要+1
            int greaterTime = Math.max(location, l - location + 1);
            int letterTime = Math.min(location, l - location + 1);
            // 更新答案
            max = Math.max(greaterTime, max);
            // 注意全部士兵下桥的最短时间为每个士兵最小花费（从左边下还是右边下的较小值）的最大值
            min = Math.max(letterTime, min);
        }
        // 输出
        out.print((min) + " " + (max));
        out.flush();
    }
    // 读入整数
    private static int readInt() {
        int in = Integer.MIN_VALUE;
        try {
            st.nextToken();
            in = (int) st.nval;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return in;
    }
}