//算法中带限期作业排序问题

#include <iostream.h>
#include "iomanip.h"

void JOB_S(int n,int *D);

void main()
{
 int *D,*P;
 int i,n;
 cout<<"请输入要处理的作业数n:";
 cin>>n;
 D=new int[n+1]; 
 P=new int[n+1]; 
 cout<<"请输入作业i的期限值D(1-"<<n<<")"<<endl;
 for(i=1;i<=n;i++)             
 {
  cout<<"作业"<<i<<"的期限：";
  cin>>D[i];
 }
 cout<<endl;
 cout<<"请输入作业i的效益值P(1-"<<n<<")"<<endl;
 for(i=1;i<=n;i++)            
 {
  cout<<"作业"<<i<<"的效益：";
  cin>>P[i];
 }
 cout<<endl;

 JOB_S(n,D);
}
void JOB_S(int n,int *D)
{
 int i,k,r;
 int *J=new int[n+1];
 k=1;
 D[0]=0;
 J[0]=0;
 J[1]=1;
 
 for(i=2;i<=n;i++)
 {
  r=k;
  while(D[J[r]]>D[i] && D[J[r]]!=r)
   r=r-1;
  if(D[J[r]]<=D[i] && D[i]>r)
  {
   for(int x=k;x>=r+1;x--)
    J[x+1]=J[x];
   J[r+1]=i;
   k++;
  }
 }
 cout<<"该作业的最优处理顺序为:";
 for(i=1;i<=k;i++)
  cout<<setw(4)<<J[i];
 cout<<endl;}