Problem 1472 --进程调度

1472: 进程调度

上一题 正确率: $82.76\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $29$ 正确数量 $24$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心 结构体

Description

操作系统的一个重要功能是进行进程调度，其进程调度的算法有多种，其中最简单的调度算法是先来先服务（FCFS）算法。该算法的思想是：先进入就绪队列的先执行，后进入就绪队列的后执行，同一时刻进入就绪队列的执行时间少的先执行。我们认为某一进程一旦开始执行，就一直占用处理机，直到执行结束。而一旦处理机被其它进程占用，就绪队列中的进程就必须等待。当某一进程执行结束后，队列中排在最前面的进程就会立即执行。一个进程从进入就绪队列到执行完毕所用的时间为其周转时间，即周转时间=等待时间+执行时间。现在给你若干进程到达就绪队列的时间以及每个队列的执行时间，请编程计算这些进程的平均周转时间。

Input

多组测试数据。
每组测试数据的第一行为一个正整数N（N<=1000），表示要处理的进程数目。
接下来有N行，每行有两个正整数Ai（Ai<=1000）和Ei（Ei<=1000），分别表示一个进程到达就绪队列的时刻和执行该进程所需的时间。

Output

对于每组测试数据，输出平均周转时间，结果保留4位小数。
每组输出占一行。

Sample Input复制

4
1 1
3 3
2 2
4 4

Sample Output复制

3.5000

提示


进程1等待时间为0，执行时间为1，其周转时间为0+1=1；
进程3等待时间为0，执行时间为2，其周转时间为0+2=2；
进程2等待时间为1，执行时间为3，其周转时间为1+3=4；
进程4等待时间为3，执行时间为4，其周转时间为3+4=7；
故平均周转时间=(1+2+4+7)/4=3.5000。

推荐代码 查看1472 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$0 $ms] MisakaNet 665388 2020-11-21 17:49:07
内存最少[$944 $KB] 2016112978 244442 2018-05-13 11:16:39
第一AC 未实名用户 88689 2017-05-13 21:08:29
第一挑战 未实名用户 88689 2017-05-13 21:08:29

赛题来源/所属竞赛 2013 Anhui College Student Programming Contest N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
AOJ