Luogu P2278 [HNOI2003]操作系统【优先队列/重载运算符/模拟】 By cellur925

65 阅读 0 评论 43 点赞

我是靠谱客的博主洁净柠檬，最近开发中收集的这篇文章主要介绍Luogu P2278 [HNOI2003]操作系统【优先队列/重载运算符/模拟】 By cellur925，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目传送门

本来是照着二叉堆的题去做的...没想到捡了个模拟...不过模拟我都不会...我好弱啊...

其实核心代码并不长，比辰哥的标程短到不知哪里去..。但是思路需要清晰。

读题的时候我明白，当有优先级高的任务来时，要把原先的任务用时减去当前已做的，再把它插进堆。

难点是更新当前的时间，以及让程序循环起来而不陷入死循环。

Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 
 5 using namespace std;
 6 
 7 int a,b,c,d,n,pos;
 8 struct cellur{
 9     int id,opt,len;
10 }item[20000];
11 priority_queue<cellur>q;
12 bool operator < (const cellur &x,const cellur &y)
13 {
14     if(x.opt==y.opt) return x.id>y.id;
15     return x.opt<y.opt;
16 }
17 
18 int main()
19 {
20     freopen("1.in","r",stdin);
21     while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
22     {
23         while(!q.empty())
24         {
25             cellur x=q.top();q.pop();
26             if(pos+x.len<=b)//新任务来前能做完当前任务 
27             {
28                 pos+=x.len;
29                 printf("%d %dn",x.id,pos);
30                 //表示堆顶任务完成了  输出 
31             }
32             else
33             {
34                 x.len-=b-pos;
35                 q.push(x);
36                 break;
37                 //原进程被打断 
38             }
39         }
40         q.push((cellur){a,d,c});
41         pos=b;//这样更新时间 
42     }
43     while(!q.empty())//把堆中元素干掉 
44     {
45         cellur x=q.top();q.pop();
46         pos+=x.len;
47         printf("%d %dn",x.id,pos);
48     }
49     return 0;
50 }