题目链接

• https://www.luogu.com.cn/problem/P1007
  

题目大意

• 有若干个士兵在长度为L的桥上，现在要求所有士兵从桥上下来花费的最小和最大时间，每次士兵只能向左或向右移动一个单位，桥上的坐标为1, 2, 3, …, L，因此士兵需要移动到0或L+1才算离开桥
  

解题思路

• 要求所有士兵从桥上下来花费的最小和最大时间
• 全部离开独木桥的最小时间，就是每个士兵都向离桥边短的方向走
• 所有士兵的下桥的最小时间为，每个士兵都采取自己下桥花费最小的方案，即计算从左边走或从右边走的时间花费的较小值，然后从中选取出花费时间最大的士兵的时间，就是所有士兵下桥的最小时间
• 全部士兵下桥的最短时间为每个士兵最小花费（从左边下还是右边下的较小值）的最大值
• 最大时间就是每个士兵都向离桥边远的方向走，此时离桥边最远的那个士兵耗费的时间就是最大时间
  • 虽然说，假如有 2 个人相向而行在桥上相遇，那么他们 2 个人将无法绕过对方，只能有 1 个人回头下，让另一个人先通过。
  • 但是两个人相遇，回头，可以看成两个人进行了灵魂交换，这样子可以看成两个人都还是按照之前的方向移动
• 注意：士兵需要移动到0或L+1才算离开桥
  

解题代码

// 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，没有士兵需要下，花费时间为0int 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需要+1int 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;}}