比赛题解 总结

1.[HNOI2003] 操作系统

思路

此题是一道大模拟，主要根据任务优先级来计算最后执行此任务的时间，此时我们可以进行分类讨论：

• 当此任务的到达时间大于等于上一个未执行完任务的结束时间，上一个任务就一定能运行完，因此直接上个结束时间
• 当此任务的到达时间小于上一个未执行完任务的结束时间，上一个任务就只能在 CPU 中运行一段时间，因此只能更新执行时间
  因为执行任务要看其优先级，因此我们用优先队列来存所有进入过 CPU 但还未运行完的任务，然后根据其优先级排序。

注意

我们需要用个变量 lati 来总时间，因此本文中的上一个 "上一个未执行完任务的结束时间" 是指 lati + 任务的执行时间

AC代码

点开有惊喜

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
struct node{ll id,be,ti,yx;bool operator < (const node &a)const{if(yx==a.yx) return be>a.be;return yx<a.yx;}
}a;
ll lati;
priority_queue<node> q;
int main(){while(scanf("%lld%lld%lld%lld",&a.id,&a.be,&a.ti,&a.yx)!=EOF){while(q.size()&&q.top().ti+lati<=a.be){node b=q.top();q.pop();cout<<b.id<<" "<<lati+b.ti<<"\n";lati+=b.ti;}if(q.size()){node b=q.top();q.pop();b.ti-=a.be-lati;q.push(b);}q.push(a);lati=a.be;}while(q.size()){node b=q.top();q.pop();lati+=b.ti;cout<<b.id<<" "<<lati<<"\n";}return 0;
}