[HNOI2003]操作系统(优先队列,堆排序)
2024-08-26 23:35:43
题目描述
写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU,每一个进程的到达时间,执行时间和运行优先级都是已知的。其中运行优先级用自然数表示,数字越大,则优先级越高。
如果一个进程到达的时候CPU是空闲的,则它会一直占用CPU直到该进程结束。除非在这个过程中,有一个比它优先级高的进程要运行。在这种情况下,这个新的(优先级更高的)进程会占用CPU,而老的只有等待。
如果一个进程到达时,CPU正在处理一个比它优先级高或优先级相同的进程,则这个(新到达的)进程必须等待。
一旦CPU空闲,如果此时有进程在等待,则选择优先级最高的先运行。如果有多个优先级最高的进程,则选择到达时间最早的。
输入输出格式
输入格式:
输入包含若干行,每一行有四个自然数(均不超过10^8),分别是进程号,到达时间,执行时间和优先级。不同进程有不同的编号,不会有两个相同优先级的进程同时到达。输入数据已经按到达时间从小到大排序。输入数据保证在任何时候,等待队列中的进程不超过15000个。
输出格式:
按照进程结束的时间输出每个进程的进程号和结束时间。
思路:
很良心的一道省选题啊,一个堆就解决了(可比什么蚯蚓良心多了)
我们由题目知道,当前CPU运算的程序一定是所有等待的进程中优先级最高的,我们用一个二叉堆来维护这个优先关系
当前时间如果有一个进程等待处理,那他会遇到3种情况:
1.没有进程在运行:那就让这个新进程运行
2.有进程在运行且优先级更高:新进程进入等待区
3.有进程在运行且优先度更低(此时可以证明新进程优先度一定比等待区的高,如果低的化运行的就不会是这个旧进程):旧进程的完成时间减去已经运行的时间,之后旧进程进入等待区,新进程开始运行
优先度关系我们用一个堆来维护
代码:
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct jc{
int num,t,y;
}cx;
int n,tim,a,b,c,d;
priority_queue<jc> q;
bool operator < (jc a,jc b)
{
if(a.y!=b.y)
{
return a.y<b.y;
}
return a.num>=b.num;
}
int main()
{
while(~scanf("%d%d%d%d",&a,&b,&c,&d))
{
while(!q.empty())
{
cx=q.top();
q.pop();
if((tim+cx.t)<=b)
{
tim+=cx.t;
printf("%d %d\n",cx.num,tim);
}
else
{
cx.t-=(b-tim);
q.push(cx);
break;
}
}
cx.y=d;
cx.num=a;
cx.t=c;
q.push(cx);
tim=b;
}
while(!q.empty())
{
cx=q.top();
q.pop();
tim+=cx.t;
printf("%d %d\n",cx.num,tim);
}
}
最新文章
- Leetcode 笔记 117 - Populating Next Right Pointers in Each Node II
- struts2中错误There is no Action mapped for namespace [/] and action name [] associated with context path
- 魔法禁书目录2:回家(codevs 3024)
- 开启Github之旅
- IIS7下,flush无效,解决方案
- EvnetBus
- HTMLParser获取属性名
- wpf单实例运行
- storm的功能、三大应用
- iOS触摸事件深度解析-备用
- man手册导出成txt,pdf,html的一些小技巧
- 不可或缺的企业OA面临问题,以及解决建议 软件定制开发 森普演示平台
- C# 控件的缩写
- R语言︱SNA-社会关系网络 R语言实现专题(基础篇)(一)
- Vue-CLI和脚手架
- PCB差分线学习
- cornerstone 使用-图标含义-分支-合并
- iOS .tdb代替.dylib
- 【转】C/C++函数调用过程分析
- 三个和数组有关的程序题目(C++)