GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
GoldenPotato的ACM小屋
一名HITer/LLer/ACMer的ACM(前OI)博客
  1. 首页
  2. 数据结构
  3. 堆
  4. 正文

[Luogu P2278] [HNOI2003]操作系统

2019年02月12日 363点热度 0人点赞 0条评论

题面

传送门:洛咕


Solutiton

挺简单的一道模拟题,拿堆模拟一下题目意思就好

堆中有两个关键字,分别是优先级和到达时间

还要维护一下每个任务剩余时间(还有多久完成)

因为堆不能直接改.得在堆里记录编号然后映射出来

这里总结一下要注意的细节:

1.在下一个任务到达之前,尽可能把CPU内的任务完成了

2.注意读入

3.注意注释文件读写233(我因为这破事爆零一次)

4.没了

好像不需要记录到达时间,编号即为到达时间先后

但懒得改了


Code

//Luogu P2278 [HNOI2003]操作系统
//May,4th,2018
//堆+模拟
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1000000;
int t[N];
struct op
{
    int a,no,at;
    friend bool operator < (op A,op B)
    {
        if(A.a==B.a)
            return A.at > B.at;
        return A.a < B.a;
    }
};
priority_queue <op,vector<op> > d;
int main()
{
    //freopen("system.in","r",stdin);
    int no,at,T,a,t_now=0;
    while(scanf("%d%d%d%d",&no,&at,&T,&a)==4)
    {
        while(d.empty()==false)
        {
            op now=d.top();
            if(t[now.no]<=at-t_now)
            {
                d.pop();
                t_now+=t[now.no];
                printf("%d %d\n",now.no,t_now);
            }
            else
            {
                t[now.no]-=at-t_now;
                break;
            }
        }
        op temp;
        temp.no=no,temp.a=a,temp.at=at,t[no]=T;
        d.push(temp);
        t_now=at;
    }

    while(d.empty()==false)
    {
        op now=d.top();
        d.pop();
        t_now+=t[now.no];
        printf("%d %d\n",now.no,t_now);
    }
    return 0;
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 堆 数据结构 模拟
最后更新:2019年02月12日

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

点赞
下一篇 >

文章评论

取消回复

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 33
  • 22
  • 79,009
  • 22,847

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号