題目描述
如果你認為參加一個編程比賽讓你感到有壓力，那么請你想象你是一個空中交通管制員。因為人命關天，所以一個空中交通管制員必須在時刻變化的環境中專注于任務，解決不可預知的事件。
讓我們將目光轉向飛機的著陸流程。飛機進入目的地飛航情報區之后，就會報告自己的位置、方向和速度，然后管制員就需要制定計劃讓所有飛機按指令安全著陸。一般來說，連續的兩次著陸之間間隔時間越長，就越安全。因為這些額外的時間能夠讓工程師有機會對天氣變化以及其他突發事件作出反應。
幸運的是，有一部分計劃的制定可以自動化——這就是你來這里的原因。你會得到有關飛機著陸的腳本。每一個飛機都有一個安全著陸時間窗。你算出的指令必須要符合每個飛機的時間窗。另外，飛機的著陸時間點要盡量均勻，使得連續兩次著陸的最小間隔盡量大。例如，如果三架飛機分別著陸于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<bits/stdc++.h> #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;i<=n;i++){s+=x;if(s>p[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;i<=n;i++){scanf("%d%d",&p[i].x,&p[i].y);num[i]=i;}double ans=0;do{double l=0,r=1440,mid;//要用double類型，說實話，沒有想到。while(r-l>esp){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;printf("Case %d: %d:%02d\n",++k,(int)(ans/60),(int)(fmod(ans,60)+0.5));}return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]A Careful Approach（全排列+二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。