[HNOI2003]操作系统

嘟嘟嘟

这道题就是一个模拟。

首先我们建一个优先队列，存所有等待的进程，当然第一关键字是优先级从大到小，第二关键字是到达时间从小到大。然后再建一个指针Tim，代表cpu运行的绝对时间。

然后分一下几种情况：

1.如果等待队列为空，那直接调到当前该执行的进程的到达时间，并把它放进等待队列（可以这么理解，每一个进程运行完之前都要进入等待队列）。

2.如果非空，还要分两种情况：

　　(1).当前队首的进程 j 能在当前该执行的进程 i 到达前运行完，那么就把 j 踢出队列，并输出，Tim 加上 j 的运行时间。

　　(2).j 在 i 之前运行不完，那么 j 在 i 到达之前能运行多少，就把他的运行时间减去多少，然后把 i 和 j 都放进队列里。

总的来说，Tim 指针每一次总是跳到最近的时间点，然后执行当前优先级最高的进程。这样有的进程就可能不是一次执行完，不过这并不影响，因为如果他的优先级高的话，一定会在下一个循环中继续执行。

这个循环的终止条件是将所有的进程都放进了等待队列里，所以只用在循环外面每一次输出队首的进程就行了。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<cctype>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a) memset(a, 0, sizeof(a))

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 const int maxn = 1e7 + ;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) last = ch, ch = getchar();

     while(isdigit(ch)) ans = (ans << ) + (ans << ) + ch - '', ch = getchar();

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) putchar('-'), x = -x;

     if(x >= ) write(x / );

     putchar(x %  + '');

 }

 struct Node

 {

     int id, com, tim, lev;

     bool operator < (const Node& other)const

     {

         return lev < other.lev || (lev == other.lev && com > other.com);

     }

 }a[maxn];

 priority_queue<Node> q;

 int n = ;

 int main()

 {

 //    freopen("ha.in", "r", stdin);

     while(scanf("%d%d%d%d", &a[n + ].id, &a[n + ].com, &a[n + ].tim, &a[n + ].lev) != EOF) n++;

     int Tim = ;

     int i = ;

     while(i <= n)

     {

         if(q.empty()) Tim = a[i].com, q.push(a[i]), i++;    //case 1

         else

         {

             Node now = q.top(); q.pop();

             if(Tim + now.tim <= a[i].com)                    //case 2.1

             {

                 Tim += now.tim;

                 write(now.id); space; write(Tim); enter;

             }

             else                                            //case 2.2

             {

                 now.tim -= a[i].com - Tim;

                 Tim = a[i].com;

                 q.push(now); q.push(a[i]); i++;

             }

         }

     }

     while(!q.empty())

     {

         Node now = q.top(); q.pop();

         Tim += now.tim;

         write(now.id); space; write(Tim); enter;

     }

     return ;

 }