[蓝桥杯][算法提高VIP]A Careful Approach（全排列+二分）
28 浏览量
2021-01-06
08:18:48
上传
评论
收藏 57KB PDF 举报
[蓝桥杯蓝桥杯][算法提高算法提高VIP]A Careful Approach（全排列（全排列+二分）二分）
题目描述
如果你认为参加一个编程比赛让你感到有压力，那么请你想象你是一个空中交通管制员。因为人命关天，所以一个空中交通管
制员必须在时刻变化的环境中专注于任务，解决不可预知的事件。
让我们将目光转向飞机的着陆流程。飞机进入目的地飞航情报区之后，就会报告自己的位置、方向和速度，然后管制员就需要
制定计划让所有飞机按指令安全着陆。一般来说，连续的两次着陆之间间隔时间越长，就越安全。因为这些额外的时间能够让
工程师有机会对天气变化以及其他突发事件作出反应。
幸运的是，有一部分计划的制定可以自动化——这就是你来这里的原因。你会得到有关飞机着陆的脚本。每一个飞机都有一个
安全着陆时间窗。你算出的指令必须要符合每个飞机的时间窗。另外，飞机的着陆时间点要尽量均匀，使得连续两次着陆的最
小间隔尽量大。例如，如果三架飞机分别着陆于10:00am、10:05am、10:15am，那么最小间隔是五分钟，在头两架飞机之
间。所有间隔不一定一样，但是最小的间隔要尽量大。
输入
多组数据。每个数据第一行为一个整数n，为飞机架数。接下来n行，每行两个整数a[i]，b[i]表示这架飞机只能在闭区间
[a[i],b[i]]间降落。a[i]和b[i]的单位是分钟。输入的最后一行是一个零。
输出
对于每组数据，先输出第几组，然后输出最小间隔，单位为分和秒，舍入到最近的整数。格式参见样例。
样例输入
3
0 10
5 15
10 15
2
0 10
10 20
0
样例输出
Case 1: 7:30
Case 2: 20:00
思路：dotcpp网站上没有给出数据范围，数据很少，n最大只有8.最小距离最大化，很明显是二分的思路，但是我们没有办法
知道飞机的降落顺序，因此就没有办法求出最优解。因为数据量很小，所以我们枚举所有的降落顺序，然后二分去找最小的间
隔，不断的更新最终答案。
代码如下：
#include
#define ll long long
#define esp 1e-7
using namespace std;
const int maxx=10;
struct node{
int x,y;
}p[maxx];
int num[maxx];
int n;
inline bool check(double x)
{
double s=p[num[1]].x;
for(int i=2;ip[num[i]].y) return 0;//这里代表间隔太大了，就不符合题意
if(s<p[num[i]].x) s=p[num[i]].x;//这里代表间隔太小了，但是这样符合题意，因为我们枚举的最小间隔
}
return 1;
}
int main()
{
int k=0;
while(scanf("%d",&n),n)
{
for(int i=1;iesp)
{
mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
ans=max(ans,r);
}while(next_permutation(num+1,num+1+n));
ans*=60;
资源评论
