问题描述
出于好奇，我被检查出的问题，设置为2009年ACM国际大学生程序设计竞赛。这些问题是pretty的有趣。他们可以在 http://cm.baylor.edu/resources/pdf/2009Problems。 PDF 。我不能想出一种算法，解决的问题1，我将在这里重现。它掀起的办公室进行了热烈讨论，而且我们认为我们是pretty的接近答案，但我们真的很AP preciate它，如果有人能找到/制定出一个完整的解决方案（code不要求）。
我将在这里重现问题，为您提供方便：
问题1
考虑安排那些降落在机场的飞机的任务。传入的飞机报告他们的位置，方向，和速度，然后控制器必须制定一个登陆时间表，将所有飞机安全着陆。一般情况下，有更多的时间有连续的平台之间，在安全着陆时间表。这额外的时间，使飞行员的机会，以应对不断变化的天气和其他的惊喜。幸运的是，这种调度任务的一部分可以实现自动化 - 这就是你进来，你会得到飞机着陆的情景。每架飞机有一个时间窗口，在此期间，它可以安全着陆。你必须计算的订单落地尊重这些时间窗口的所有飞机。此外，飞机着陆应伸出尽可能使连续着陆之间的最小时间间隔是尽可能的大。例如，如果三个飞机降落在上午10:00，上午10:05和10:15，然后最小的差距是五分钟，其中前两个飞机之间发生。不是所有的间隙必须是相同的，但最小的间隙应尽可能地大。
输入
输入文件中包含多个测试案例包括着陆的情景描述。每个测试例开始使用包含单个整数线的 N 的（2≤的 N 的≤8），这是在场景中的飞机的数量。其次是 N 的行，每行包含两个整数的在 ， B 的]，在此期间我的日飞机安全着陆。这些数字的在我 和 B 我 的以分钟指定，满足0≤在我 的≤ B 我 的≤1440。输入终止与含有单个整数零的线。
输出
对于每个测试用例的输入，打印其随后相继平台之间的最小可实现时间上的差距编号（从1开始）。打印时间分成分秒，四舍五入到最接近的第二位。按照样本输出的格式。
采样输入
3
0 10
5月15日
10 15
2
0 10
10 20
0
示例输出
案例1：07：30
案例2：20：00
我会做这样的事情：
的#include＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
＃包括＆LT; string.h中＆GT;
的typedef UINT面膜;
＃定义INPUT_SCALE 60
＃定义MAX_TIME（1440 * 60）
无效readPlaneData（INT和放大器; endTime的，MASK landingMask [MAX_TIME]，INT指数）
{
焦炭BUF [128];
得到（BUF）;
INT开始，结束;
sscanf的（BUF，％D，与功放;启动，和放大器端）;
对于（INT I =启动* INPUT_SCALE; I＆LT; =结束* INPUT_SCALE;我++）
landingMask [我] | = 1＆LT;＆LT;指数;
如果（完* INPUT_SCALE＆GT; endTime的）
endTime的=结束* INPUT_SCALE;
}
INT findNextLandingForPlane（MASK landingMask [MAX_TIME]，诠释开始，诠释指数）
{
同时（开始＆LT; MAX_TIME）
{
如果（landingMask [开始]及（1＆LT;＆LT;指数））
返回启动;
启动++;
}
返回-1;
}
布尔canLandPlanes（INT minTime，MASK landingMask [MAX_TIME]，INT planeCount）
{
INT下一= 0;
的for（int i = 0; I＆LT; planeCount;我++）
{
INT nextForPlane = findNextLandingForPlane（landingMask，接下来我）;
如果（nextForPlane == -1）
返回false;
接下来= nextForPlane + minTime;
}
返回true;
}
INT主（INT ARGC，字符* argv的[]）
{
而（真）
{
焦炭BUF [128];
得到（BUF）;
诠释计数=的atoi（BUF）;
如果（计数== 0）
打破;
MASK landingMask [MAX_TIME]
memset的（landingMask，0，sizeof的（landingMask））;
INT endTime的= 0;
的for（int i = 0; I＆LT;计数;我++）
readPlaneData（endTime的，landingMask，我）;
而（（endTime的＆GT; 0）及和放大器;！canLandPlanes（endTime的，landingMask，计数））
时间结束 - ;
的printf（％D：％02D \ N，endTime的/ 60，endTime的60％）;
}
}
Out of curiosity, I was checking out the problem set to the 2009 ACM International Collegiate Programming Contest. The questions are pretty interesting. They're available at http://cm.baylor.edu/resources/pdf/2009Problems.pdf. I could not come up with an algorithm that solved problem 1, which I will reproduce here. It set off a lively discussion in the office, and we think we're pretty close to an answer, but we'd really appreciate it if somebody could find/work out a full solution (code not required).
I will reproduce problem here for your convenience:
Problem 1
Consider the task of scheduling the airplanes that are landing at an airport. Incoming airplanes report their positions, directions, and speeds, and then the controller has to devise a landing schedule that brings all airplanes safely to the ground. Generally, the more time there is between successive landings, the "safer" a landing schedule is. This extra time gives pilots the opportunity to react to changing weather and other surprises.Luckily, part of this scheduling task can be automated – this is where you come in. You will be given scenarios of airplane landings. Each airplane has a time window during which it can safely land. You must compute an order for landing all airplanes 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 three airplanes land at 10:00am, 10:05am, and 10:15am, then the smallest gap is five minutes, which occurs between the first two airplanes. Not all gaps have to be the same, but the smallest gap should be as large as possible.
Input
The input file contains several test cases consisting of descriptions of landing scenarios. Each test case starts with a line containing a single integer n (2 ≤ n ≤ 8), which is the number of airplanes in the scenario. This is followed by n lines, each containing two integers a, b, which give the beginning and end of the closed interval [a, b] during which the ith plane can land safely. The numbers a and b are specified in minutes and satisfy 0 ≤ a ≤ b ≤ 1440.The input is terminated with a line containing the single integer zero.
Output
For each test case in the input, print its case number (starting with 1) followed by the minimum achievable time gap between successive landings. Print the time split into minutes and seconds, rounded to the closest second. Follow the format of the sample output.
Sample Input
3
0 10
5 15
10 15
2
0 10
10 20
0
Sample Output
Case 1: 7:30
Case 2: 20:00
I would do something like this:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef uint MASK;
#define INPUT_SCALE 60
#define MAX_TIME (1440 * 60)
void readPlaneData(int& endTime, MASK landingMask[MAX_TIME], int index)
{
char buf[128];
gets(buf);
int start, end;
sscanf(buf, "%d %d", &start, &end);
for(int i=start * INPUT_SCALE; i<=end * INPUT_SCALE; i++)
landingMask[i] |= 1 << index;
if(end * INPUT_SCALE > endTime)
endTime = end * INPUT_SCALE;
}
int findNextLandingForPlane(MASK landingMask[MAX_TIME], int start, int index)
{
while(start < MAX_TIME)
{
if(landingMask[start] & (1 << index))
return start;
start++;
}
return -1;
}
bool canLandPlanes(int minTime, MASK landingMask[MAX_TIME], int planeCount)
{
int next = 0;
for(int i=0; i<planeCount; i++)
{
int nextForPlane = findNextLandingForPlane(landingMask, next, i);
if(nextForPlane == -1)
return false;
next = nextForPlane + minTime;
}
return true;
}
int main(int argc, char* argv[])
{
while(true)
{
char buf[128];
gets(buf);
int count = atoi(buf);
if(count == 0)
break;
MASK landingMask[MAX_TIME];
memset(landingMask, 0, sizeof(landingMask));
int endTime = 0;
for(int i=0; i<count; i++)
readPlaneData(endTime, landingMask, i);
while((endTime > 0) && !canLandPlanes(endTime, landingMask, count))
endTime--;
printf("%d:%02d\n", endTime / 60, endTime % 60);
}
}
这篇关于从2009年ACM-ICPC全球总决赛飞机调度的挑战的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！