Description

写一个程序来模拟操作系统的进程调度. 假设该系统只有一个 CPU, 每一个进程的到达时间, 执行时间和运行优先级都是已知的. 其中运行优先级用自然数表示, 数字越大, 则优先级 越高. 如果一个进程到达的时候 CPU 是空闲的, 则它会一直占用 CPU 直到该进程结束. 除非在这个过程中, 有一个比它优先级高的进程要运行. 在这种情况下, 这个新的 (优先级更高的) 进程会占用 CPU, 而老的只有等待. 如果一个进程到达时, CPU 正在处理一个比它优先级高或优先级相同的进程, 则这个 (新到达的) 进程必须等待. 一旦 CPU 空闲, 如果此时有进程在 等待, 则选择优先级最高的先运行. 如果有多个优先级最高的进程, 则选择到达时间最早的.

Input

输入文件包含若干行, 每一行有四个自然数 (均不超过 \(10^8\)) , 分别是进程号, 到达 时间, 执行时间和优先级. 不同进程有不同的编号, 不会有两个相同优先级的进程同时到达. 输入数据已经按到达时间从小到大排序. 输入数据保证在任何时候, 等待队列中的进程不超过 \(15000\) 个.

Output

按照进程结束的时间输出每个进程的进程号和结束时间.

Sample Input

1 1 5 3
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4

Sample Output

1 6
3 19
5 30
6 32
8 34
4 35
7 40
2 42

Explanation

严格意义上来说就是一道 \(O(n \log n)\) 的模拟题. 每一次用堆维护一个优先权最大的任务, 然后不停插入弹出或者再插入 (如果那个任务没有新加入的任务优先级高的话).

其实 STL 就可以水过了...... 但是读入没有 \(n\) 实在太坑, 好久都没有用过 while EOF 了, 现在都生疏了~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 300200;
const lli infinit = 1000000000ll;

struct process_t {
    lli proc_id, priority;
    lli begin_time, exec_time;
};
bool operator < (process_t a, process_t b) {
    if (a.priority == b.priority)
        return a.begin_time > b.begin_time;
    return a.priority < b.priority; }
bool cmp(process_t a, process_t b) {
    return a.begin_time < b.begin_time; }

struct result_typ {
    lli proc_id, end_time;
    result_typ(lli& _, lli& __) { proc_id = _; end_time = __; }
    result_typ() { proc_id = end_time = 0; }
};
bool comp(result_typ a, result_typ b) {
    return a.end_time < b.end_time; }

int n;
process_t proc[maxn];
result_typ res[maxn];
// lli res[maxn];

int main(int argc, char** argv)
{
    lli a, b, c, d;
    while (scanf("%lld", &a) != EOF) {
        scanf("%lld%lld%lld", &b, &c, &d);
        n += 1;
        proc[n].proc_id = a;
        proc[n].begin_time = b;
        proc[n].exec_time = c;
        proc[n].priority = d;
    }
    // Add (useless) process.
    proc[n+1].proc_id = 0;
    proc[n+1].begin_time = infinit;
    proc[n+1].exec_time = 0;
    proc[n+1].priority = 0;
    // Sorting according to arrival time.
    sort(proc + 1, proc + 1 + n, cmp);
    // for (int i = 1; i <= n; i++) {
    //     printf("%lld %lld %lld %lld\n",
    //         proc[i].proc_id,
    //         proc[i].begin_time,
    //         proc[i].exec_time,
    //         proc[i].priority
    //     );
    // }
    // Adding processes to CPU.
    priority_queue<process_t> pq;
    lli cur_time = 0;
    for (int i = 1; i <= n+1; i++) {
        lli req_time = proc[i].begin_time - cur_time;
        // printf("req %lld top exec %lld\n", req_time, !pq.empty() ? pq.top().exec_time : -1);
        while (!pq.empty() && pq.top().exec_time <= req_time) {
            process_t t_proc = pq.top();
            // printf("ejecting %lld\n", t_proc.proc_id);
            cur_time += t_proc.exec_time;
            res[t_proc.proc_id] = result_typ(
                t_proc.proc_id, cur_time);
            req_time -= t_proc.exec_time;
            pq.pop();
        }
        // Termination sequences
        if (i >= n+1)
            break;
        // Rejecting last worse task
        if (!pq.empty() && req_time > 0) {
            process_t o_proc = pq.top();
            pq.pop();
            o_proc.exec_time -= req_time;
            pq.push(o_proc);
        }
        // Injecting this object.
        process_t n_proc = proc[i];
        cur_time = n_proc.begin_time;
        pq.push(n_proc);
    }
    // Output results
    sort(res + 1, res + n+1, comp);
    for (int i = 1; i <= n; i++)
        printf("%lld %lld\n", res[i].proc_id, res[i].end_time);
    return 0;
}