做集团网站,太原seo顾问,为什么要做官方网站,抖音开放平台题目描述
如果你认为参加一个编程比赛让你感到有压力#xff0c;那么请你想象你是一个空中交通管制员。因为人命关天#xff0c;所以一个空中交通管制员必须在时刻变化的环境中专注于任务#xff0c;解决不可预知的事件。 让我们将目光转向飞机的着陆流程。飞机进入目的地飞…题目描述
如果你认为参加一个编程比赛让你感到有压力那么请你想象你是一个空中交通管制员。因为人命关天所以一个空中交通管制员必须在时刻变化的环境中专注于任务解决不可预知的事件。 让我们将目光转向飞机的着陆流程。飞机进入目的地飞航情报区之后就会报告自己的位置、方向和速度然后管制员就需要制定计划让所有飞机按指令安全着陆。一般来说连续的两次着陆之间间隔时间越长就越安全。因为这些额外的时间能够让工程师有机会对天气变化以及其他突发事件作出反应。 幸运的是有一部分计划的制定可以自动化——这就是你来这里的原因。你会得到有关飞机着陆的脚本。每一个飞机都有一个安全着陆时间窗。你算出的指令必须要符合每个飞机的时间窗。另外飞机的着陆时间点要尽量均匀使得连续两次着陆的最小间隔尽量大。例如如果三架飞机分别着陆于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;}
}
