2010-1120

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

'''题目大意'''[[BR]]
机场航班控制。给定某天到达DoIt和离开DoIt的航班信息，然后模拟航班升降。
限制：跑道N条，每条跑道被使用后需要一段时间后才能被再次使用。时间与相邻两航班的类型相关。
没有可使用跑道的时候飞机会在上空盘旋排队等待下降指令或在地面等待起飞指令。
若干查询，要求某个时间机场出发大厅显示牌的信息。
其它若干规则，请认真读题...= =

'''解法'''[[BR]]
就是一个mg题，读题是关键，把规则读懂就好。
唯一需要处理的是控制航班起降时间gao()。可以用个priority_queue来处理。
由于跑道数比较少，所以每次要安排起降时间的时候可以扫描每条跑道，找到最优的。

加强版：
跑道数很多，飞机类型数不变。可以每种类型对应一个set。set中元素表示最后一次使用该跑道的类型为当前类型的跑道的使用时间。
然后安排跑道时可以直接比较每个set的begin()，找到最优安排。

'''代码'''
{{{
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
using namespace std;

const int MAXN = 110;
const int MAXM = 25;

int DAY[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int year, month, day, COST[MAXM][MAXM], N;
priority_queue<pair<int, pair<int, int> > > pq;
pair<int, int> runway[MAXN];

inline void showTime(int now) {
    int hh = now / 60, mm = now % 60;
    printf("%02d:%02d", hh, mm);
}

inline void showDate(int year, int month, int day) {
    printf("%04d-%02d-%02d", year, month, day);
}

inline bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}

inline void showNextDate(int year, int month, int day) {
    if (isLeap(year)) DAY[2] = 29;
    if (day < DAY[month]) {
        day++;
    } else if (month < 12) {
        month++, day = 1;
    } else {
        year++, month = 1, day = 1;   
    }
    showDate(year, month, day);
    DAY[2] = 28;
}

class Flight {
public:
    string FN, DEST;
    int AT, ETA, ETD, SD, DT;

    void init() {
        char st[20];
        int a, b, c;
        scanf("%s", st);
        FN = st;
        scanf("%d", &AT);
        scanf("%d-%d-%d", &a, &b, &c);
        scanf("%d:%d", &a, &b);
        ETA = a * 60 + b;
        scanf("%d:%d", &a, &b);
        SD = a * 60 + b;
        scanf("%d-%d-%d", &a, &b, &c);
        scanf("%d:%d", &a, &b);
        ETD = a * 60 + b;
        if (c != day) {
            ETD += 24 * 60;
        }
        scanf("%s", st);
        DEST = st;
        DT = ETD;
    }

    void show(int now) {
        printf("%s ", FN.c_str());
        if (DT >= 24 * 60) {
            showNextDate(year, month, day);
            putchar(' ');
            showTime(DT - 24 * 60);
            putchar(' ');
        } else {
            showDate(year, month, day);
            putchar(' ');
            showTime(DT);
            putchar(' ');   
        }
        printf("%s ", DEST.c_str());
        if (DT <= now) {
            puts("LEAVE");
        } else if (DT <= ETD) {
            puts("ON TIME");   
        } else {
            puts("DELAY");   
        }
    }

};

vector<Flight> v;

bool cmp(const Flight &a, const Flight &b) {
    return a.ETA == b.ETA ? a.FN < b.FN : a.ETA < b.ETA;
}

void gao(int now, int type) {
    if (type == 4) {
        // put-down request
        int early = 24 * 60 * 2, go;
        for (int i = 1; i <= N; i++) {
            int cur = runway[i].first + COST[runway[i].second][v[now].AT];
            cur = max(cur, v[now].ETA);
            if (early > cur) {
                early = cur;
                go = i;
            }   
        }
        runway[go] = make_pair(early, v[now].AT);
        v[now].DT = max(v[now].DT, early + v[now].SD);
        pq.push(make_pair(-v[now].DT, make_pair(3, -now)));
        return;
    }

    if (type == 3) {
        // take-off request
        int early = 24 * 60 * 2, go;
        for (int i = 1; i <= N; i++) {
            int cur = runway[i].first + COST[runway[i].second][v[now].AT];
            cur = max(cur, v[now].DT);
            if (early > cur) {
                early = cur;
                go = i;
            }               
        }   
        runway[go] = make_pair(early, v[now].AT);
        v[now].DT = max(v[now].DT, early);
        return;
    }
}

int main() {

    int M, F, Q, hh, mm;
    while (scanf("%d-%d-%d", &year, &month, &day) != EOF) {

        assert(1980 <= year && year <= 2099);
        assert(1 <= month && month <= 12);
        if (isLeap(year)) DAY[2] = 29;
        assert(1 <= day && day <= DAY[month]);
        DAY[2] = 28;

        scanf("%d %d %d", &N, &M, &F);
        assert(1 <= N && N <= 100);
        assert(1 <= M && M <= 20);
        assert(1 <= F && F <= 10000);

        for (int i = 1; i <= N; i++) {
            runway[i] = make_pair(0, 0);
        }
        memset(COST, 0, sizeof(COST));
        for (int i = 1; i <= M; i++)
            for (int j = 1; j <= M; j++) {
                scanf("%d", &COST[i][j]);
                assert(1 <= COST[i][j] && COST[i][j] <= 100);
            }
        v.clear();
        while (!pq.empty()) pq.pop();
        Flight tmp;
        for (int i = 1; i <= F; i++) {
            tmp.init();
            v.push_back(tmp);
            assert(1 <= v[i - 1].AT && v[i - 1].AT <= M);

        }
        sort(v.begin(), v.end(), cmp);
        for (int i = 0; i < F; i++) {
           pq.push(make_pair(-v[i].ETA, make_pair(4, -i)));        
        }
        showDate(year, month, day); putchar('\n');
        scanf("%d", &Q);
        assert(1 <= Q && Q <= 20);
        for (int i = 0; i < Q; i++) {
            scanf("%d:%d", &hh, &mm);
            int now = hh * 60 + mm;
            assert(now >= 6 * 60 && now < 24 * 60);

            while (!pq.empty() && -pq.top().first <= now) {               
                int type = pq.top().second.first, ind = -pq.top().second.second;
                pq.pop();
                gao(ind, type);   
            }
            showTime(now); putchar('\n');
            for (int j = 0; j < F; j++) {
                v[j].show(now);   
            }
            putchar('\n');
        }
    }
    return 0;    
}


}}}

题目大意

机场航班控制。给定某天到达DoIt和离开DoIt的航班信息，然后模拟航班升降。

限制：跑道N条，每条跑道被使用后需要一段时间后才能被再次使用。时间与相邻两航班的类型相关。

没有可使用跑道的时候飞机会在上空盘旋排队等待下降指令或在地面等待起飞指令。

若干查询，要求某个时间机场出发大厅显示牌的信息。

其它若干规则，请认真读题...= =

解法

就是一个mg题，读题是关键，把规则读懂就好。

唯一需要处理的是控制航班起降时间gao()。可以用个priority_queue来处理。

由于跑道数比较少，所以每次要安排起降时间的时候可以扫描每条跑道，找到最优的。

加强版：

跑道数很多，飞机类型数不变。可以每种类型对应一个set。set中元素表示最后一次使用该跑道的类型为当前类型的跑道的使用时间。

然后安排跑道时可以直接比较每个set的begin()，找到最优安排。

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
using namespace std;
const int MAXN = 110;
const int MAXM = 25;
int DAY[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int year, month, day, COST[MAXM][MAXM], N;
priority_queue<pair<int, pair<int, int> > > pq;
pair<int, int> runway[MAXN];
inline void showTime(int now) {
    int hh = now / 60, mm = now % 60;
    printf("%02d:%02d", hh, mm);
}
inline void showDate(int year, int month, int day) {
    printf("%04d-%02d-%02d", year, month, day);
}
inline bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}
inline void showNextDate(int year, int month, int day) {
    if (isLeap(year)) DAY[2] = 29;
    if (day < DAY[month]) {
        day++;
    } else if (month < 12) {
        month++, day = 1;
    } else {
        year++, month = 1, day = 1;   
    }
    showDate(year, month, day);
    DAY[2] = 28;
}
class Flight {
public:
    string FN, DEST;
    int AT, ETA, ETD, SD, DT;
    void init() {
        char st[20];
        int a, b, c;
        scanf("%s", st);
        FN = st;
        scanf("%d", &AT);
        scanf("%d-%d-%d", &a, &b, &c);
        scanf("%d:%d", &a, &b);
        ETA = a * 60 + b;
        scanf("%d:%d", &a, &b);
        SD = a * 60 + b;
        scanf("%d-%d-%d", &a, &b, &c);
        scanf("%d:%d", &a, &b);
        ETD = a * 60 + b;
        if (c != day) {
            ETD += 24 * 60;
        }
        scanf("%s", st);
        DEST = st;
        DT = ETD;
    }
    void show(int now) {
        printf("%s ", FN.c_str());
        if (DT >= 24 * 60) {
            showNextDate(year, month, day);
            putchar(' ');
            showTime(DT - 24 * 60);
            putchar(' ');
        } else {
            showDate(year, month, day);
            putchar(' ');
            showTime(DT);
            putchar(' ');   
        }
        printf("%s ", DEST.c_str());
        if (DT <= now) {
            puts("LEAVE");
        } else if (DT <= ETD) {
            puts("ON TIME");   
        } else {
            puts("DELAY");   
        }
    }
};
vector<Flight> v;
bool cmp(const Flight &a, const Flight &b) {
    return a.ETA == b.ETA ? a.FN < b.FN : a.ETA < b.ETA;
}
void gao(int now, int type) {
    if (type == 4) {
        // put-down request
        int early = 24 * 60 * 2, go;
        for (int i = 1; i <= N; i++) {
            int cur = runway[i].first + COST[runway[i].second][v[now].AT];
            cur = max(cur, v[now].ETA);
            if (early > cur) {
                early = cur;
                go = i;
            }   
        }
        runway[go] = make_pair(early, v[now].AT);
        v[now].DT = max(v[now].DT, early + v[now].SD);
        pq.push(make_pair(-v[now].DT, make_pair(3, -now)));
        return;
    }
    if (type == 3) {
        // take-off request
        int early = 24 * 60 * 2, go;
        for (int i = 1; i <= N; i++) {
            int cur = runway[i].first + COST[runway[i].second][v[now].AT];
            cur = max(cur, v[now].DT);
            if (early > cur) {
                early = cur;
                go = i;
            }               
        }   
        runway[go] = make_pair(early, v[now].AT);
        v[now].DT = max(v[now].DT, early);
        return;
    }
}
int main() {
    int M, F, Q, hh, mm;
    while (scanf("%d-%d-%d", &year, &month, &day) != EOF) {
        assert(1980 <= year && year <= 2099);
        assert(1 <= month && month <= 12);
        if (isLeap(year)) DAY[2] = 29;
        assert(1 <= day && day <= DAY[month]);
        DAY[2] = 28;
        scanf("%d %d %d", &N, &M, &F);
        assert(1 <= N && N <= 100);
        assert(1 <= M && M <= 20);
        assert(1 <= F && F <= 10000);
        for (int i = 1; i <= N; i++) {
            runway[i] = make_pair(0, 0);
        }
        memset(COST, 0, sizeof(COST));
        for (int i = 1; i <= M; i++)
            for (int j = 1; j <= M; j++) {
                scanf("%d", &COST[i][j]);
                assert(1 <= COST[i][j] && COST[i][j] <= 100);
            }
        v.clear();
        while (!pq.empty()) pq.pop();
        Flight tmp;
        for (int i = 1; i <= F; i++) {
            tmp.init();
            v.push_back(tmp);
            assert(1 <= v[i - 1].AT && v[i - 1].AT <= M);
        }
        sort(v.begin(), v.end(), cmp);
        for (int i = 0; i < F; i++) {
           pq.push(make_pair(-v[i].ETA, make_pair(4, -i)));        
        }
        showDate(year, month, day); putchar('\n');
        scanf("%d", &Q);
        assert(1 <= Q && Q <= 20);
        for (int i = 0; i < Q; i++) {
            scanf("%d:%d", &hh, &mm);
            int now = hh * 60 + mm;
            assert(now >= 6 * 60 && now < 24 * 60);
            while (!pq.empty() && -pq.top().first <= now) {               
                int type = pq.top().second.first, ind = -pq.top().second.second;
                pq.pop();
                gao(ind, type);   
            }
            showTime(now); putchar('\n');
            for (int j = 0; j < F; j++) {
                v[j].show(now);   
            }
            putchar('\n');
        }
    }
    return 0;    
}