#include<stdio.h>
typedef struct PCB{
  int ID;    //进程ID 
  double submit;     //提交时间 
  double run;    //运行时长 
  double start;  //开始时间 
  double end;    //结束时间 
  double TAT;  //周转
  double TATW;    //带权周转
}PCB;
void FCFS(PCB pcb[], int PCBNUM){      
  //先来先服务
  PCB temp;  //方便交换 
  for(int i = 0; i < PCBNUM - 1; i++){                 
    for(int j = 0; j < PCBNUM - i - 1; j++){
      if(pcb[j].submit > pcb[j+1].submit){
        //使用冒泡排序，通过提交时间经行排序 
        temp = pcb[j];
          pcb[j] = pcb[j+1];
        pcb[j+1] = temp;
      }
      }
    }
  for(int i = 0; i < PCBNUM; i++){    
    //时间计算
    if(i == 0){
      pcb[i].start = pcb[i].submit;
    }
    else{
      pcb[i].start = pcb[i-1].end;
    }
    pcb[i].end = pcb[i].start + pcb[i].run;
    pcb[i].TAT = pcb[i].end - pcb[i].submit;
    pcb[i].TATW = pcb[i].TAT / pcb[i].run;
  }
  printf("FCFS，先来先服务算法：\n");
  printf("名称    提交    运行    开始    结束    周转    带权周转\n");
  for(int i = 0; i < PCBNUM; i++){   
      //输出
    printf("%d\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\n", pcb[i].ID, pcb[i].submit, pcb[i].run, pcb[i].start, pcb[i].end, pcb[i].TAT, pcb[i].TATW);
  }
  printf("\n");
}
void SPF(PCB pcb[], int PCBNUM){     
  //短进程优先 
  PCB temp;  //方便交换 
  for(int r = PCBNUM - 1; r > 0; r--){
    //选出第一行
    if(pcb[r-1].submit > pcb[r].submit){
      temp = pcb[r];
        pcb[r] = pcb[r-1];
      pcb[r-1] = temp;
    }
  }
  for(int i = 1; i < PCBNUM - 1; i++){        
    for(int j = 1; j < PCBNUM - 1; j++){
      //通过运行时间排序 
      if(pcb[j].run > pcb[j+1].run ){
        temp = pcb[j];
          pcb[j] = pcb[j+1];
        pcb[j+1] = temp;
      }
      }
  }
  for(int i = 0; i < PCBNUM; i++){     //计算
    if(i == 0){
      pcb[i].start = pcb[i].submit;
    }
    else{
      pcb[i].start = pcb[i-1].end;
    }
    pcb[i].end = pcb[i].start +pcb[i].run;
    pcb[i].TAT = pcb[i].end -pcb[i].submit;
    pcb[i].TATW = pcb[i].TAT/pcb[i].run ;    
  }
  printf("SPF，短进程优先算法：\n");
  printf("名称    提交    运行    开始    结束    周转    带权周转\n");
  for(int i = 0; i < PCBNUM; i++){   
      //输出
    printf("%d\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\n", pcb[i].ID, pcb[i].submit, pcb[i].run, pcb[i].start, pcb[i].end, pcb[i].TAT, pcb[i].TATW);
  }
  printf("\n");
}
void HRRN(PCB pcb[], int PCBNUM){          
  //高响应比
  PCB temp;  //方便交换
  int R[PCBNUM];  //记录相应比 
  for(int r = PCBNUM-1; r > 0; r--){    
      //选出第一行
    if(pcb[r-1].submit > pcb[r].submit){
      temp = pcb[r];
        pcb[r] = pcb[r-1];
      pcb[r-1] = temp;
    }
  }
  for(int i = 0; i < PCBNUM - 1; i++){               
    for(int j=1;j < PCBNUM - 1; j++){
      //排序，通过响应比 
      for(int o = 1; o < PCBNUM; o++){     
         //计算响应比
        R[i] = (pcb[i-1].end-pcb[i].submit) / pcb[i].run+1;
      }
      if(R[i] < R[i+1]){
        temp = pcb[j];
          pcb[j] = pcb[j+1];
        pcb[j+1] = temp;
      }
    }
  }
  for(int i = 0; i < PCBNUM; i++){     
    //计算
    if(i == 0){
      pcb[i].start = pcb[i].submit;
    }
    else{
      pcb[i].start = pcb[i-1].end;
    }
    pcb[i].end = pcb[i].start + pcb[i].run;
    pcb[i].TAT = pcb[i].end - pcb[i].submit;
    pcb[i].TATW = pcb[i].TAT / pcb[i].run;
    }
    printf("HRRN，高响应比算法：\n");
    printf("名称    提交    运行    开始    结束    周转    带权周转\n");
  for(int i = 0; i < PCBNUM; i++){   
      //输出
    printf("%d\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\n", pcb[i].ID, pcb[i].submit, pcb[i].run, pcb[i].start, pcb[i].end, pcb[i].TAT, pcb[i].TATW);
  }
  printf("\n");
}
int main(){
  printf("请输入进程数目：");
  int PCBNUM;
  scanf("%d", &PCBNUM);
  PCB pcb[PCBNUM];  //申请空间 
  printf("请输入每个进程的进程名，提交时间，运行时长（中间用空格分开）\n"); 
  for(int i = 0; i < PCBNUM; i++){
    scanf("%d%lf%lf", &pcb[i].ID, &pcb[i].submit, &pcb[i].run);
  }
  FCFS(pcb, PCBNUM);
  SPF(pcb, PCBNUM);
  HRRN(pcb, PCBNUM);
}