#include <malloc.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NULL 0
#define N 10
typedef struct table
{  char  name[8];     /*作业名*/
   float in_well;       /*进入输入井时间*/
   float begin_run;     /*开始运行时间*/
   float run_time;      /*运行时间*/
   float end_run;       /*结束运行时间*/
   float turnover_time; /*周转时间*/
 }jobtable;

 bool compare(const jobtable &a, const jobtable &b)//比较进入时间的大小排序 
 {
    return a.in_well < b.in_well;
 }

void init(jobtable job[],int n) /*初始化作业表*/
{
   int i,j;
   printf("input %d job information\n",n);
   printf("in_well run_time name\n");
   for(i=0;i<n;i++)
   {
       scanf("%f %f %s",&job[i].in_well,&job[i].run_time,job[i].name);//输入各个作业的进入时间，运行时间，名字 
       job[i].begin_run=0.0;//初始化各个作业的开始时间 
       job[i].end_run=0.0;//初始化各个作业的结束时间 
       job[i].turnover_time=0.0;//初始化各个作业的周转时间 
   } 
   std :: sort(job, job + n, compare);//排序进入时间 
}

void print (jobtable job[],int n)  /*输出链表*/
{  int i;
   printf("name  in_well  run_time  begin_run  end_run  turnover_time\n");
   for(i=0;i<n;i++)
   {  printf("%s\t%0.1f\t%0.1f\t",job[i].name,job[i].in_well,job[i].run_time);
      if(job[i].begin_run==0.0&&job[i].end_run==0.0&&job[i].turnover_time==0.0)//如果各个数据都为空则输出空字符串 
        printf("                                \n");
      else
      printf("%9.1f%9.1f\t%0.1f\n",job[i].begin_run,job[i].end_run,job[i].turnover_time);
   }
}

 void swap(jobtable job[],int p,int q)//交换程序 
{    float temp1;
     char temp2[8];
     strcpy(temp2,job[p].name);strcpy(job[p].name,job[q].name);strcpy(job[q].name,temp2);//用strcpy函数交换名字 
     temp1=job[p].in_well;job[p].in_well=job[q].in_well;job[q].in_well=temp1;//交换p,q的进入时间位置 
     temp1=job[p].run_time;job[p].run_time=job[q].run_time;job[q].run_time=temp1;//交换p,q的运行时间 
 }

 float response_ratio(jobtable job[],int n)/*模拟当前作业表的调度过程*/
 {   int i,j,temp;
     float average_time,ratio1,ratio2;
     job[0].begin_run=job[0].in_well;//第一个作业的进入时间就是它的开始时间 
     job[0].end_run=job[0].begin_run+job[0].run_time;//同理第一个作业的结束时间就是运行时间+开始时间 
     job[0].turnover_time=job[0].end_run-job[0].begin_run;//计算第一个作业的周转时间（结束时间-开始时间） 
     average_time=job[0].turnover_time;//平均周转时间先加上第一个作业的周转时间 
     for(i=1;i<n;i++)//开始遍历其他的作业 
     {  if(job[i].in_well<=job[i-1].end_run)//如果下一个作业的进入时间在前一个作业结束前到达时进入 
        {  j=i+1;temp=i;
           ratio1=1+(job[i-1].end_run-job[i].in_well)*1.0/job[i].run_time;//计算下一个作业的响应比 
           while(j<n&&job[j].in_well<=job[i-1].end_run)//遍历之后所有能进入下一次调度作业的响应比 
           {  
              ratio2=1+(job[i-1].end_run-job[j].in_well)*1.0/job[j].run_time;
              if(ratio2>ratio1)  
              {
                ratio1 = ratio2; 
                temp=j;//如果比最大的响应比高则记录j的位置并且将ratio1更改 
              }
              j++;
           }
           if(temp!=i)  //如果temp指向不是初始位置就交换两个作业的顺序 
              swap(job,i,temp);
        }
      job[i].begin_run=job[i-1].end_run;//下一个作业的开始时间就是前一个作业的结束时间 
      job[i].end_run=job[i].begin_run+job[i].run_time;//下一个作业时间的结束时间是开始运行时间+运行时间 
      job[i].turnover_time=job[i].end_run-job[i].in_well;//该作业的周转时间就是结束时间-进入时间 
      average_time=average_time+job[i].turnover_time;//平均周转时间+该作业的周转时间 
    }
    return(average_time/n);//返回平均周转时间 
 }


 int main()
 {  int n;//作业的数量 
    float ave_turnover_time;//平均周转时间 
    jobtable job[N];//作业的数据 
    printf("input job numbers\n");
    scanf("%d",&n);
    if(n<=N)//总作业数量不超过N 
    {  
       printf("按照进入输入井的先后顺序初始化作业表 \n");
       init(job,n);//初始化作业表 
       printf("initial station \n");
       print(job,n);//输出作业初始的数据 
       ave_turnover_time=response_ratio(job,n);//计算全部作业的平均周转时间 
       printf("termination station \n");
       print(job,n);
       printf("ave_turnover_time is:%12.1f\n",ave_turnover_time);
    }
   else  printf("error!\n"); 
 }