2009 ACM-ICPC世界总决赛带来的飞机调度挑战

小编典典

2009 ACM-ICPC世界总决赛带来的飞机调度挑战

algorithm

出于好奇，我正在检查2009
ACM国际大学编程竞赛的问题。这些问题很有趣。可在 http://cm.baylor.edu/resources/pdf/2009Problems.pdf上找到它们。我无法提出解决问题1的算法，我将在这里重现。它在办公室引起了热烈的讨论，我们认为我们已经很接近答案了，但是如果有人可以找到/制定出完整的解决方案（不需要代码），我们将不胜感激。

为了方便起见，我将在此处重现问题：

问题1

考虑安排在机场降落的飞机的任务。进来的飞机报告其位置，方向和速度，然后管制员必须制定着陆时间表，以使所有飞机安全着陆。通常，连续降落之间的时间越长，降落时间表越“安全”。这些额外的时间使飞行员有机会对天气变化和其他意外做出反应。幸运的是，可以自动执行此计划任务的一部分-
这就是您要进入的地方。您将获得飞机着陆的场景。每架飞机都有一个可以安全着陆的时间窗。您必须计算遵守这些时间窗口的所有飞机着陆的命令。此外，飞机的着陆区应尽可能伸展，以使连续着陆之间的最小时间间隔尽可能大。例如，如果三架飞机分别在上午10:00，上午10:05和上午10:15降落，则最小间隔为五分钟，这是前两架飞机之间的间隔。并非所有间隙都必须相同，但最小的间隙应尽可能大。

输入项

输入文件包含几个测试用例，其中包含着陆方案的描述。每个测试用例开始于包含单个整数的线 Ñ （2≤ Ñ ≤8），这是在场景中的飞机的数量。接下来是
n 条线，每条线包含两个整数 a i， b i，给出了第 i 个平面可以安全着陆的闭合间隔[ a i， b i ]
的开始和结束。数字一个我和 b 我以分钟指定和满足0≤ 一个我 ≤ b 我
≤1440。输入终止与含有单个整数零的线。

输出量

对于输入中的每个测试用例，请打印其用例编号（以1开头），然后打印连续着陆之间可达到的最小时间间隔。打印时间分为分钟和秒，四舍五入到最接近的秒。遵循示例输出的格式。

样本输入

样本输出

Case 1: 7:30
Case 2: 20:00

阅读 287

2020-07-28

共1个答案

小编典典

我会做这样的事情：

#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);
    }
}

2020-07-28