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;
}
