区块链技术博客
www.b2bchain.cn

Airplane Landing Problem

这篇文章主要介绍了Airplane Landing Problem,通过具体代码讲解7741并且分析了Airplane Landing Problem的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了Airplane Landing Problem。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=7741。具体如下:

Problem Description

With human lives at stake, an air traffic controller has to schedule the airplanes that are landing at an airport in order to avoid airplane collision. Each airplane iihas a time window [si,ti][si,ti] during which it can safely land. You must compute the exact time of landing for each airplane that respects these time windows. Furthermore, the airplane landings should be stretched out as much as possible so that the minimum time gap between successive landings is as large as possible.

For example, if the time window of landing three airplanes are [10:00-11:00], [11:20-11:40], [12:00-12:20], and they land at 10:00, 11:20, 12:20 respectively, then the smallest gap is 60 minutes, which occurs between the last two airplanes.

Given 5 time windows, denoted as [s1,t1],[s2,t2],⋯,[s5,t5][s1,t1],[s2,t2],⋯,[s5,t5] satisfying 0<=s1<t1<s2<t2<⋯<s5<t5<=240<=s1<t1<s2<t2<⋯<s5<t5<=24. You are required to give the exact landing time of each airplane, in which the smallest gap between successive landings is maximized.

Notice:

Make sure that each airplane lands as early as possible.

Input

10 numbers(type is float32) s1,t1,s2,t2,⋯,s5,t5s1,t1,s2,t2,⋯,s5,t5, satisfying 0<=s1<t1<s2<t2<⋯<s5<t5<=240<=s1<t1<s2<t2<⋯<s5<t5<=24.

Output

5 numbers(type is float32) l1,l2,⋯,l5l1,l2,⋯,l5, with accuracy of two decimal digits.

Sample Input

1 2 3 4 5 6 7 8 9 10

Sample Output

1.00 3.25 5.50 7.75 10.00

 

 #include <iostream> #include<cmath> #include<vector> using namespace std;  int n, m; double BE[6], EN[6]; const double eps = 1e-6;   vector<double>  ve;  int dcmp(double x) { 	if (fabs(x)<eps) return 0; 	return x>0 ? 1 : -1; }   bool can(double ans) {  	ve.clear(); 	double last = BE[1]; ve.push_back(last);  	for (int i = 2; i <= 5; i++) 	{ 		double ret = last + ans;  		if (dcmp(ret - EN[i])>0)  return false;  		if (dcmp(ret - BE[i]) <= 0)  last = BE[i]; 		else  last = ret;  		ve.push_back(last);  	}  	return true;   }   double solve() {  	double le = 0, ri = EN[5] - BE[1];  	while (le + eps<ri) 	{ 		double mid = (le + ri) / 2; 		if (!can(mid)) ri = mid; 		else le = mid; 	}  	double mid = (le + ri) / 2; 	can(mid); 	return mid;  } int main() {   	while (cin >> BE[1] >> EN[1] >> BE[2] >> EN[2] >> BE[3] >> EN[3] >> BE[4] >> EN[4] >> BE[5] >> EN[5]) 	{ 		double ans = solve();  		for (int i = 0; i<5; i++)  printf("%.2f%c", ve[i], i == 4 ? 'n' : ' ');  	}  	return 0; } 

 

本文地址https://www.b2bchain.cn/?p=7741

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » Airplane Landing Problem
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们