「BZOJ1216」[HNOI2003] 操作系统
Description
写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。如果一个进程到达的时候CPU是空闲的，则它会一直占用CPU直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用CPU，而老的只有等待。如果一个进程到达时，CPU正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。一旦CPU空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。
Input
输入文件包含若干行，每一行有四个自然数（均不超过108），分别是进程号，到达时间，执行时间和优先级。不同进程有不同的编号，不会有两个相同优先级的进程同时到达。输入数据已经按到达时间从小到大排序。输入数据保证在任何时候，等待队列中的进程不超过15000个。
Output
按照进程结束的时间输出每个进程的进程号和结束时间
Sample Input
1 1 5 3
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4
Sample Output
1 6
3 19
5 30
6 32
8 34
4 35
7 40
2 42
3 19
5 30
6 32
8 34
4 35
7 40
2 42
题解
用堆模拟一下就能水过了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<algorithm> #define pa pair<int,int> #define inf 100000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int x,now; int t1[300005],t2[300005],rk[300005]; int st[300005],ed[300005]; struct data{int id,t;}; struct res{int id,t;}ans[300005]; priority_queue<data,vector<data> >q; bool operator<(data a,data b) { if(rk[a.id]==rk[b.id])return t1[a.id]>t1[b.id]; return rk[a.id]<rk[b.id]; } bool operator<(res a,res b) { return a.t<b.t; } int main() { while(scanf("%d",&x)!=EOF) { t1[x]=read();t2[x]=read();rk[x]=read(); ans[x].id=x; } t1[x+1]=inf; for(int i=1;i<=x+1;i++) { int t=t1[i]-now; while(!q.empty()&&q.top().t<=t) { now+=q.top().t; ans[q.top().id].t=now; t-=q.top().t; q.pop(); } if(i==x+1)break; if(!q.empty()&&t) { data x=q.top();q.pop(); x.t-=t; q.push(x); } now=t1[i]; q.push((data){i,t2[i]}); } sort(ans,ans+x+1); for(int i=1;i<=x;i++) printf("%d %d\n",ans[i].id,ans[i].t); return 0; } |
Subscribe
计数器 9855190
OI 课件=>
OI 课件=>