#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef long long ll;
struct JOB
{char name[20]; //作业名字int arrival_time; //到达时间int start_time; //开始时间int end_time; //结束时间int run_time; //预计运行时间int res_time; //剩余运行时间int average_wait; //平均等待时间int average_zhou; //平均周转时间int real_start; //第一次开始的时间int level; //优先级int state; //状态，是否已经结束double weight_zhou;
};
vector<JOB> process(100); //保存每个输入的作业的信息
vector<JOB> out; //保存每个时间段的作业信息
int current_time=0; //当前时间
int flag=0; //标记是否所有作业已经结束int time_change(int x,int y) //将输入的时间转换成分钟形式
{return x*60+y;
}
void re_change(int x) //时间格式逆转换
{int hour;int mint;hour=x/60;mint=x%60;if(mint==0) printf("%d:00 ",hour);else printf("%d:%d ",hour,mint);
}
int get_current_process(int t) //获取当前时间t，应该是哪个进程开始执行
{int p_id=-1;int max_lev=0;flag=0;int ltime=10000000;for(int i=1;i<=process.size();i++){if(process[i].state==1) flag++; //统计有多少进程结束了if(process[i].arrival_time<=t&&process[i].state!=1) //找出到达时间小于当前时间且还没结束的进程{if(process[i].level>max_lev) //优先选择优先级高的{p_id=i;max_lev=process[i].level;}if(process[i].level==max_lev) //如果优先级一致，则看谁先到{if(process[i].arrival_time<ltime){p_id=i;ltime=process[i].arrival_time;}}}}return p_id;
}
int main()
{double pjzz=0,dqpj=0;int n;scanf("%d",&n); //输入有多少个作业for(int i=1;i<=n;i++) //输入信息，依次输入 名字，到底时间，运行时间，等级{int hour,mint,cost,lev;scanf("%s %d:%d %d %d",process[i].name,&hour,&mint,&cost,&lev);process[i].arrival_time=time_change(hour,mint);process[i].run_time=cost;process[i].res_time=cost;process[i].level=lev;process[i].start_time=process[i].end_time=process[i].state=0; //初始化}current_time=process[1].arrival_time; //设置当前时间为第一个作业到达的时间while(1){int p=get_current_process(current_time); //获取当前是哪个作业可以执行if(flag==n) break; //如果全部结束了则跳出循环if(p==-1) current_time++; //当前时间没有进程则时间加1else{if(process[p].start_time==0) //如果当前作业是第一次执行{process[p].start_time=current_time;process[p].real_start=current_time;if(out.size()!=0&&out[out.size()-1].end_time==0){out[out.size()-1].end_time=current_time; //上一个作业的结束时间就是当前时间}out.push_back(process[p]); //将当前进程加入到输出的队列里}current_time+=process[p].run_time;process[p].res_time=0; //剩余时间减少if(process[p].res_time==0) //如果执行完了{process[p].end_time=current_time; //赋值保存结束时间process[p].average_zhou=current_time-process[p].arrival_time; //计算周转时间process[p].weight_zhou=(1.0*process[p].average_zhou)/(1.0*process[p].run_time);JOB tmp;tmp=process[p];if(strcmp(out[out.size()-1].name,process[p].name)==0){out[out.size()-1].end_time=current_time; //如果当前进程没有被打断过，则直接修改，不用再添加。}else{tmp.start_time=out[out.size()-1].end_time; //否则就上一个作业的结束时间就是当前作业的开始时间out.push_back(tmp); //加入到输出队列}process[p].state=1; //标记当前作业已经结束了}}}printf("\n调度运行过程:作业名字,作业开始时间,作业结束时间,作业等级\n");for(auto x: out){printf("%s ",x.name);re_change(x.start_time);re_change(x.end_time);printf("%d\n",x.level);}printf("\n");printf("调度结果:作业名字,作业开始时间,作业结束时间,作业周转周期\n");for(int i=1;i<=n;i++){printf("%s ",process[i].name);re_change(process[i].real_start);re_change(process[i].end_time);printf("%d %.2f\n",process[i].average_zhou,process[i].weight_zhou);pjzz+=1.0*process[i].average_zhou;dqpj+=1.0*process[i].weight_zhou;}printf("平均周转时间、带权平均周转时间\n");printf("%.2f %.2f\n",pjzz/(1.0*n),dqpj/(1.0*n));return 0;
}