洛谷 - P2278 - 操作系统 - 模拟

https://www.luogu.org/problemnew/show/P2278

题目没有说同时到达的优先级最大的应该处理谁。

讲道理就是处理优先级最大的。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Process {

    int id;

    int itime;

    int dtime;

    int pri;

    inline bool operator<(const Process& p)const {

        if(pri==p.pri)

            //大根堆，大的先出，符号反向

            return itime>p.itime;

        else

            return pri<p.pri;

    }

    inline bool pri_less_than(const Process &p) {

        return pri<p.pri;

    }

    inline void input(int &i,int &it,int &dt,int &p) {

        id=i;

        itime=it;

        dtime=dt;

        pri=p;

    }

} p,cur;

priority_queue<Process> pq;

ll curtime,deltatime,pretime,nexttime;

void show_state() {

    printf("ptime=%lld  ctime=%lld  dtime=%lld\n",pretime,curtime,deltatime);

    printf(" curid=%d  curdtime=%d\n",cur.id,cur.dtime);

    printf(" pq.size=%d\n",(int)pq.size());

    printf("\n");

}

void change_process() {

    if(pq.empty())

        return;

    if(cur.id==0) {

        //puts("next process!");

        cur=pq.top();

        pq.pop();

        nexttime=curtime+cur.dtime;

        //show_state();

    } else if(cur.pri_less_than(pq.top())) {

        //puts("change process!");

        //命令保存当前进程并取出新进程，更新时间

        pq.push(cur);

        cur=pq.top();

        pq.pop();

        nexttime=curtime+cur.dtime;

        //show_state();

    }

}

void do_process() {

    //puts("do process!");

    if(cur.id==0)

        return;

    //show_state();

    ll mintime=min(deltatime,(ll)cur.dtime);

    deltatime-=mintime;

    pretime+=mintime;

    cur.dtime-=mintime;

    if(cur.dtime==0) {

        printf("%d %lld\n",cur.id,pretime);

        cur.id=0;

        nexttime=-1;

    }

    //show_state();

}

void update() {

    do {

        do_process();

        //当前进程做不完了，堆顶是不是有比它大的？

        change_process();

    } while(cur.id&&deltatime);

    //CPU正忙，尽可能从堆里面取出进程

}

int main() {

#ifdef Yinku

    freopen("Yinku.in","r",stdin);

#endif // Yinku

    int id,itime,dtime,pri;

    scanf("%d%d%d%d",&id,&itime,&dtime,&pri);

    curtime=itime;

    pretime=itime;

    deltatime=curtime-pretime;

    p.input(id,itime,dtime,pri);

    pq.push(p);

    update();

    while(~scanf("%d%d%d%d",&id,&itime,&dtime,&pri)) {

        while(cur.id&&itime>nexttime) {

            //puts("!");

            pretime=curtime;

            curtime=nexttime;

            deltatime=curtime-pretime;

            update();

        }

        //puts("?");

        if(cur.id==0)

            pretime=itime;

        else

            pretime=curtime;

        curtime=itime;

        deltatime=curtime-pretime;

        p.input(id,itime,dtime,pri);

        pq.push(p);

        update();

    }

    pretime=curtime;

    curtime=1e18;

    deltatime=curtime-pretime;

    update();

    return 0;

}