【六十七】【算法分析与设计】[HNOI2003]操作系统,优先队列,自定义比较方式,模拟,提高输入输出效率之神奇小代码,初始化小技巧

[HNOI2003]操作系统

链接：登录—专业IT笔试面试备考平台_牛客网 来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。

如果一个进程到达的时候CPU是空闲的，则它会一直占用CPU直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用CPU，而老的只有等待。

如果一个进程到达时，CPU正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。一旦CPU空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。

输入描述:

输入文件包含若干行，每一行有四个自然数（均不超过108），分别是进程号，到达时间，执行时间和优先级。不同进程有不同的编号，不会有两个相同优先级的进程同时到达。

输入数据已经按到达时间从小到大排序。输入数据保证在任何时候，等待队列中的进程不超过15000个。

输出描述:

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

示例1

输入

复制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

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

输出

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

1 6

3 19

5 30

6 32

8 34

4 35

7 40

2 42

1.

每一次只走一小步,循环这一小步然后变成无穷的步数,从而完成问题解答.

2.

初始化小技巧

小技巧,对于题目输入的数据,定义对应的变量进行存储,自定义一个init()初始化函数,用来接收输入的数据,进行存储.

定义的数据存储变量需要在全局.尽可能在全局.

3.

优先队列自定义比较方式,operator<

优先队列默认是大根堆,也就是队列顶端是最大的元素,想要改变"大"的定义,只需要重载类的<符号即可.

在优先队列中，C++ STL 的 priority_queue 类默认是使用 operator< 运算符来进行元素的比较和排序的，而不是使用 operator>。因此，如果您尝试在优先队列中重载 operator> 运算符，可能会导致编译错误.

因此我们只能重载operator<符号.

可以想象A,B两个process对象正在比较谁在优先队列前面谁在优先队列后面.

A

在C++中，operator<用于定义对象的小于关系，通常用于排序和比较。在你提供的代码片段中，这个操作符被重载来定义process对象如何在优先队列（priority_queue）中排序。

bool operator<(const process& p)const {
    if (priority != p.priority)
        return priority < p.priority;
    else {
        return start_time > p.start_time;
    }
}

在这段代码中，operator<定义了如下的逻辑：

1. 比较优先级：首先比较两个进程的priority。在优先队列中，C++默认是最大堆，也就是说，队列顶部是最大元素。在这个定义中，当this->priority小于p.priority时，返回true。这意味着，如果当前对象的优先级较低，则它在优先队列中的位置会更靠后（更小），从而实现了一个最大优先队列，其中优先级更高的进程会先被处理。

1. 处理相同优先级：如果两个进程的优先级相同（即priority != p.priority的结果为false），则会比较start_time。在这里，代码使用start_time > p.start_time。这意味着，如果当前进程的到达时间较晚，则它被视为较小（因为要返回true）。这确保了当多个进程具有相同的优先级时，到达时间更早的进程将在优先队列中更靠前。

总结：

• 当进程优先级不同，优先级高的进程视为较大。

• 当进程优先级相同，到达时间早的进程视为较大。

这种设计使得优先队列可以优先处理高优先级的进程，且在优先级相同的情况下，先到达的进程先得到处理。这符合典型的实时操作系统或任务调度的预期行为，其中希望尽快处理高优先级任务，同时在有多个同样重要的任务时，遵循先到先得的原则。

4.

提高输入输出效率的神奇小代码

ios::sync_with_stdio(0);

cin.tie(0);

背下来,背下来,背下来,在数据量很大的情况下,提高输入输出的效率,非常有用.

在 C++ 编程中，ios::sync_with_stdio(0) 和 cin.tie(0) 这两行代码通常用于优化输入输出操作的性能，特别是在处理大量输入输出时。让我们来详细解释这两条命令的作用：

1. ios::sync_with_stdio(0);这行代码用于关闭 C++ 输入输出流（iostream）与 C 标准输入输出流（stdio）之间的同步。默认情况下，这两个系统是同步的，以保证你可以在同一个程序中混用 C++ 的 cin/cout 和 C 的 scanf/printf 而不会出现问题（如输出顺序错误）。关闭同步后，iostream 可以独立于 stdio 运行，这通常会使得 iostream 的输入输出操作更快，但你就不能再混用两种输入输出方式了。

1. cin.tie(0);默认情况下，cin 与 cout 是绑定（tied）的，这意味着每次在从 cin 读取之前，cout 的缓冲区会被自动刷新，以确保按顺序进行读写操作。通过执行 cin.tie(0);，你解除了这种绑定，这样 cin 和 cout 就不会再自动刷新对方的缓冲区了。这通常可以减少不必要的刷新操作，从而提高程序的输入输出性能。

总结，这两条命令在处理有大量输入输出需求的情况下非常有用，比如在算法竞赛中快速读写数据。但使用时要注意，一旦使用这些优化措施，就不能再混用 C 和 C++ 的标准输入输出函数了，并且需要自己控制输出的时机，特别是在输出之前确保所有必要的输入已经读取完毕。

5.

只考虑走一步的情况,循环走一步,等价于走无穷步.

#include
using namespace std;
using ll = long long;
using p = pair<int, int>;
 
// 定义一个进程类，包含进程ID、到达时间、生命周期、优先级
class process {
public:
        process(ll _id, ll _start_time, ll _life, ll _priority)
                :id(_id), start_time(_start_time), life(_life), priority(_priority) {}
 
        ll id;
        ll start_time;
        ll life;
        ll priority;
 
        // 重载小于操作符，用于优先队列的排序
        bool operator<(const process& p)const {
                if (priority != p.priority) // 优先级不相同，按优先级高低排序
                        return priority < p.priority;
                else { // 优先级相同，按到达时间早晚排序
                        return start_time > p.start_time;
                }
        }
 
 
};
 
// 输入参数
vector process_vec;
 
// 初始化函数，从标准输入读取进程数据
void init() {
        ll id, start_time, life, priority;
 
        while (cin >> id >> start_time >> life >> priority) {
                process tmp(id, start_time, life, priority);
                process_vec.push_back(tmp);
        }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    
        init(); // 调用初始化函数读取进程数据
 
        priority_queue pq; // 优先队列，按优先级和到达时间排序进程
 
        ll index = 0; // 进程向量的索引
        ll cur_time = 0; // 当前时间
        while (index < process_vec.size()) {
                if (pq.empty()) { // 如果优先队列为空
                        cur_time = process_vec[index].start_time; // 更新当前时间为下一个进程的到达时间
                } else { // 如果优先队列不为空
                        auto top = pq.top(); // 取出优先级最高的进程
                        pq.pop();
 
                        ll diff = min(process_vec[index].start_time - cur_time, top.life); // 计算时间差
                        cur_time += diff; // 更新当前时间
                        top.life -= diff; // 减少进程的剩余生命周期
 
                        if (top.life == 0) { // 如果进程执行完毕
                                cout << top.id << " " << cur_time << endl; // 输出进程ID和结束时间
                        } else {
                                pq.push(top); // 如果进程未执行完毕，重新放回优先队列
                        }
                }
 
                while (index < process_vec.size() && process_vec[index].start_time <= cur_time) {
                        pq.push(process_vec[index++]); // 将新到达的进程放入优先队列
                }
        }
 
        while (!pq.empty()) { // 处理所有剩余的进程
                auto top = pq.top(); // 取出优先级最高的进程
                pq.pop();
 
                cur_time += top.life; // 更新当前时间
                cout << top.id << " " << cur_time << endl; // 输出进程ID和结束时间
        }
 
}

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！