蓝桥杯第1390题——A Careful Approach

题目描述

如果你认为参加一个编程比赛让你感到有压力，那么请你想象你是一个空中交通管制员。因为人命关天，所以一个空中交通管制员必须在时刻变化的环境中专注于任务，解决不可预知的事件。 让我们将目光转向飞机的着陆流程。飞机进入目的地飞航情报区之后，就会报告自己的位置、方向和速度，然后管制员就需要制定计划让所有飞机按指令安全着陆。一般来说，连续的两次着陆之间间隔时间越长，就越安全。因为这些额外的时间能够让工程师有机会对天气变化以及其他突发事件作出反应。 幸运的是，有一部分计划的制定可以自动化——这就是你来这里的原因。你会得到有关飞机着陆的脚本。每一个飞机都有一个安全着陆时间窗。你算出的指令必须要符合每个飞机的时间窗。另外，飞机的着陆时间点要尽量均匀，使得连续两次着陆的最小间隔尽量大。例如，如果三架飞机分别着陆于10:00am、10:05am、10:15am，那么最小间隔是五分钟，在头两架飞机之间。所有间隔不一定一样，但是最小的间隔要尽量大。

输入描述

多组数据。每个数据第一行为一个整数 n，为飞机架数。

接下来 n 行，每行两个整数 a[i]，b[i] ，表示这架飞机只能在闭区间 [a[i],b[i]] 间降落。

a[i]和b[i]​的单位是分钟。输入的最后一行是一个零。

2≤n≤8, 0 ≤ a[i],b[i] ≤1440, 数据组数不大于 20​。

输出描述

对于每组数据，先输出第几组，然后输出最小间隔，单位为分和秒，舍入到最近的整数。格式参见样例。

输入输出样例

示例

输入

3
0 10 
5 15 
10 15 
2 
0 10 
10 20 
0

输出

Case 1: 7:30
Case 2: 20:00

解题思路

本题的解题思路是二分法，观察到n的范围是2至8，因此我们可以选择使用二分法配合dfs暴力搜索。（2023年蓝桥杯也有一个飞机起降问题，也是类似的数据范围，可以直接暴力。）题目有一句话让我们明显想到二分法策略——“最小间隔尽量大”。

具体的说，我们可以测试一个值mid，假设最小降落间隔是t，那么用dfs暴力测试所有飞机是否可以按最小间隔为t降落。

如果t的值非常小，几乎等同于无限制，因为只要大于等于t就可以了；如果t的值非常大，那么几乎就只能有一架飞机能降落，无法让所有飞机都降落。

到这里二分就明确了，从某一个值开始，其左值都能满足要求，其右值都不能满足要求。

对于测试一个t值是否满足要求，大的框架就是使用dfs，如果飞机没有降落，那么降落时间一定要在data[i][0]和data[i][1]之间，所以首先对理想中的最优降落时间——上一架飞机的降落时间+t，与目标飞机的最早降落时间取最大值，然后再与最晚降落时间取最小值。这样就选择到了满足最小间隔t的最早降落时间。

而本题还有一个坑点，就是关于单位的问题，首先它给的是分钟却要我们精确到秒，那我们当然是用秒来二分更好，因此我们首先将所有数据放大60倍变成秒，但这样做还是会导致通过率只有57.1%，原因是对于秒数量级还要进行四舍五入。

这里作者的做法是将所有数据再放大100倍，这样可以在不改变整数二分代码的情况下多计算两位有效值，最后我们再利用一点数据格式化技巧便能进行正确的四舍五入。

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
 
public class Main {
    static int n;
    static int[][] data;
    static boolean[] visited;
    // time用于记录递归过程中当前时间，也是上一架飞机的降落时间
    static int time;
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader in = new BufferedReader(new FileReader("D:\\Downloads\\1390.in"));
        for (int t = 1; true; t++) {
            String[] temp = in.readLine().split(" ");
            n = Integer.parseInt(temp[0]);
            if (n == 0) {
                return;
            }
            data = new int[n][2];
            for (int i = 0; i < n; i++) {
                temp = in.readLine().split(" ");
                data[i][0] = Integer.parseInt(temp[0]) * 60 * 100;
                data[i][1] = Integer.parseInt(temp[1]) * 60 * 100;
            }
            int left = 0, right = 1440 * 60 * 100;
            // 在该二分结构下，right是目标答案，其值是100倍的秒
            while (left <= right) {
                int mid = left + (right - left) / 2;
                // 通过new的方式保证每次递归之前visited数组被重置
                visited = new boolean[n];
                // 将time定义为极小值，用于实现第一架飞机降落时间不受限
                time = Integer.MIN_VALUE;
                if (check(mid)) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            // 一些数据格式化转换技巧
            int ans = Integer.parseInt(String.format("%.0f", right / 100.0));
            System.out.printf("Case %d: %d:%02d\n", t, ans / 60, ans - ans / 60 * 60);
        }
    }
    public static boolean check(int t) {
        for (int i = 0; i < n; i++) {
            if (!visited[i] && time + t <= data[i][1]) {
                int temp = time;
                visited[i] = true;
                time = Math.min(Math.max(data[i][0], time + t), data[i][1]);
                if (check(t)) {
                    return true;
                } else {
                    time = temp;
                    visited[i] = false;
                }
            }
        }
        // 如果测试完了所有飞机，还有没降落的，就说明该降落顺序失败，返回重新递归
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }
}