Skip to content

11027: 【原1027】戴绿帽子的空管

题目

题目描述

author: 苏春智 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1027

Description

幽会计划

二哥如今在TNCM机场做空管。二哥不幸被分配到了进近席,进近席位要负责处理所有准备降落在机场的飞机,让他们平稳地落在跑道上。飞机降落一般遵循五边进近航图,不过在这道题目中你不需要关心什么是五边进近,只要看下面这张图。

一架飞机总是从下滑道入口(A点)开始接受二哥管制,直到降落成功(B点)。飞机不会是同一型号的,速度也不一样,所以从A点到B点所需的时间不同。二哥得小心一点,不能把事情搞砸了:(1)下滑道内不允许飞机互相超越;(2)一架飞机降落之后,至少要等待一段时间才允许下一架飞机降落(即到达B的时间间隔要大于等于一个值)。

二哥是个聪明的人,他写了一个程序来帮他控制所有飞机,然后他就可以喝茶去了。二哥的策略是:通过拒绝某些飞机进入下滑道,来保证下滑道上的飞机永远不会距离太近。也就是说,只要飞机被允许进入下滑道,就可以安全降落。

每当一架飞机来到下滑道的入口时,二哥的程序就会判断:如果允许这架飞机进入下滑道,它能否安全降落。如果能安全降落,二哥就允许他进入下滑道,否则二哥会立即要求这架飞机在A点复飞。

原则上,两架飞机不应该同时出现在A点,但这种情况显然可能出现。如果真的出现了这种情况,则说明空管局这次彻底把事情搞砸,二哥的策略显然可能是诱因。

简单来说,在未来的一段时间内,共有N架飞机要降落,他们会在Ti时刻首次出现在下滑道入口,他们从A点到B点需要的时间为Ui。如果他们被二哥命令在A点复飞,他们会在Gi分钟后再次出现在下滑道入口。飞机的安全降落间隔是S。

现在,二哥的女朋友找到你,请你计算一下每架飞机会在第几分钟完成降落。这样她可以估算出二哥什么时候下班,以便瞒着二哥去和情人去幽会。

Input Format

第一行有三个正整数N、MAX、S,表示有多少飞机,最长模拟的时间,以及安全降落时间间隔。

之后有N行,每行有三个非负整数,依次为Ti、Ui、Gi,分别表示第i架飞机的首次到达时间、从A点到B点耗时、复飞耗时。

\( N \leq 1000 \) \( MAX \leq 1000000 \) \( S \leq 1000 \) \( Ti \leq 1000000 \) ,\( Ui \leq 1000 \) ,\( Gi \leq 1000 \)

Output Format

假设在MAX时刻之前([0..MAX-1]),有飞机同时出现在了下滑道口,则输出“CHANGE BOYFRIEND”,因为飞机撞了,三哥估计要下岗了,她可以换一个男朋友了。

假设在MAX时刻之前没有飞机相撞,但模拟结束后仍然有飞机没有降落,则输出一行“GO DATING”,以表示三哥的女朋友可以放心大胆地幽会去了。

否则输出N行,每行一个整数,表示第i架飞机最终降落的时刻。

Sample Input

4 20 2
0 2 5
1 2 1
5 2 1
6 10 10

Sample Output

2
4
7
16

Sample Input

3 10 2
0 2 5
1 2 3
4 1 1

Sample Output

CHANGE BOYFRIEND

样例解释

分析:

0时刻,第一架飞机到达A,二哥允许他进入下滑道,在第2时刻降落。

1时刻,第二架飞机到达A,二哥要求他复飞,因为降落间距小于安全标准。

2时刻,第二架飞机复飞后再次回到A,二哥允许他进入下滑道,在第4时刻降落。

5时刻,第三架飞机到达A,二哥允许他进入下滑道,在第7时刻降落

6时刻,第四架飞机到达A,二哥允许他降落,在第16时刻降落。


分析:

在4时刻,第二架飞机和第三架飞机会相撞。

FineArtz's solution

/* 戴绿帽子的空管 */
#include <iostream>
#include <algorithm>
using namespace std;

class plane{
public:
    int i = 0, u = 0, g = 0;
};

plane timee[1000005];
int down[1005];
int n, m, s;

bool canDown(int t1, int t2){
    if (t2 == -1) return true;
    if ((t1 + timee[t1].u) - (t2 + timee[t2].u) >= s) return true;
    return false;
}

int main(){
    cin >> n >> m >> s;
    bool flag = false;
    for (int i = 1; i <= n; ++i){
        int t;
        plane tp;
        cin >> t >> tp.u >> tp.g;
        tp.i = i;
        if (t > m){
            flag = true;
            continue;
        }
        if (timee[t].i != 0){
            cout << "CHANGE BOYFRIEND" << endl;
            return 0;
        }
        timee[t] = tp;
    }
    int lastDown = -1;
    for (int t = 0; t <= m; ++t){
        if (timee[t].i == 0) continue;
        if (canDown(t, lastDown)){
            lastDown = t;
            int tt = t + timee[t].u;
            if (tt > m) flag = true;
            else (down[timee[t].i] = tt);
        }
        else{
            int tt = t + timee[t].g;
            if (tt > m){
                flag = true;
                continue;
            }
            if (timee[tt].i != 0){
                cout << "CHANGE BOYFRIEND" << endl;
                return 0;
            }
            timee[tt] = timee[t];
        }
    }
    if (flag) cout << "GO DATING" << endl;
    else
        for (int i = 1; i <= n; ++i)
            cout << down[i] << endl;
    return 0;
}

ligongzzz's solution

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class plane {
public:
    int id, t, u, g;

    plane(int id, int t, int u, int g) :id(id), t(t), u(u), g(g) {}

    bool operator<(const plane& other) const{
        return t > other.t;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, MAX, S;
    cin >> N >> MAX >> S;

    priority_queue<plane> qdata;
    for (int i = 0; i < N; ++i) {
        int t, u, g;
        cin >> t >> u >> g;
        qdata.push(plane(i, t, u, g));
    }

    vector<int> ans(N);
    int cur_land = -999999999;
    while (!qdata.empty()) {
        auto temp = qdata.top();
        qdata.pop();

        //判断是否相撞
        if (!qdata.empty() && qdata.top().t == temp.t) {
            cout << "CHANGE BOYFRIEND";
            return 0;
        }
        if (temp.t >= MAX) {
            cout << "GO DATING";
            return 0;
        }
        if (ans.empty() || temp.t + temp.u >= cur_land + S) {
            cur_land = ans[temp.id] = temp.t + temp.u;
        }
        else {
            qdata.push(plane(temp.id, temp.t + temp.g, temp.u, temp.g));
        }
    }

    for (auto p : ans)
        cout << p << "\n";


    return 0;
}