蓝桥训练 二分

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

解题报告：万万没想到是用二分来做，同样看原题的时候题目没有给出数据范围，没想到n那么小，那么我们不用找规律，直接全排列复杂度n!logn,枚举每个区间，注意这道题是double类型的输出，用浮点数二分的板子，重点是check函数，这种最大值最小的问题或者最小值最大的，看到基本都是二分，由于贪心，那么我们采取的点肯定越靠近该点的左边越好，因为枚举的是暂停时间k，ans是当前的位置,ans+k如果越过了下个区间，别的飞机就没机会起飞了，如果在下个左端点的左边，那么我们要更新到左端点的位置，不然下一架飞机的起飞时间就错误了
。

#include<bits/stdc++.h>
using namespace std;
const	int N=10;
struct node{
	double l;
	double r;
}q[N];
int num[N];
int n;
bool check(double x)
{
	double dis=q[num[0]].l;
	for(int i=1;i<n;i++)
	{
		if(dis+x>q[num[i]].r)	return false;
		dis+=x;
		dis=max(dis,q[num[i]].l);
	}
	return true;
}
int main()
{
	int k=0;
	while(cin>>n,n)
	{
		for(int i=0;i<n;i++)
		{
			cin>>q[i].l>>q[i].r;
			num[i]=i;
		}
		double ans=0;
		do{
			double l=0,r=1440;
			while(fabs(r-l)>1e-7)
			{
			//	cout<<l<<' '<<r<<endl;
				double mid=(l+r)/2;
				if(check(mid))	l=mid;
				else		r=mid;
			}
			ans=max(ans,r);	
		}while(next_permutation(num,num+n));
		int t=(int)ans;
		printf("Case %d: %d:%02d\n",++k,t,(int)(ans*60-t*60+0.5));
		
	}
	return 0;
 }