#include <stdio.h > 
#include <iostream.h>      
#include <malloc.h >          
int MAX(int  *D,int i, int j); 
int FIND(int *parent,int i);  
int MIN(int  n,int  m) ;
int FJS(int *D,int n,int  b,int  *J,int *Q) ;
void UNION(int *parent,int i,int j);
void Insertionsort(int  *D,int n) ;                
    void  main()       
    {       
    int *D,*J,*Q,*p,n,b,i,k;       
    cout<<"用貪心法解決一種更快作業排序問題 "<<endl;       
    cout<<"請輸入作業的數目: ";       
    cin>>n;       
    D=(int*)malloc((n+1)*sizeof(int));       
    p=(int*)malloc((n+1)*sizeof(int));       
    cout<< "\n請輸入每個作業的效益值("<<n<<"個): ";       
    for(i=1;i <=n;i++)       
    cin>>p[i];       
    Insertionsort(p,n);       
    cout<< "\n按效益值非增排序后各作業為:\n ";       
    cout<< "\n作業序號                                       效益值\n ";       
    for(i=1;i <=n;i++)       
    cout<<"J"<<i<<"                                             "<<p[i] <<endl;    
    cout<<"請輸入按效益值非增排序后各作業的截止時間("<<n<<"個): ";       
    for(i=1;i <=n;i++)       
    cin>>D[i];       
    b=MIN(n,MAX(D,1,n));       
    J=(int*)malloc((b+1)*sizeof(int));       
    Q=(int*)malloc((b+1)*sizeof(int));       
    for(i=1;i <=b;i++)       
    Q[i]=-1;       
    k=FJS(D,n,b,J,Q);       
    cout<< "\n本問題的最優解\n ";       
    cout<< "\n作業序號                                       效益值\n ";       
    for(i=1;i <=k;i++)       
    cout<<"J"<<J[i]<<"                                          "<<p[J[i]] <<endl;        
    cout<< "\n各作業的執行次序\n ";       
    cout<< "\n作業序號                                       效益值\n ";       
    for(i=1;i <=b;i++)       
    if(Q[i]!=-1)       
    cout<<"J"<<Q[i]<<"                                                               "<<p[Q[i]]<<endl;               
 }       
int  FIND(int *parent,int i)       
    {//查找含有元素i的樹根，使用壓縮規則去壓縮由i到根j的所有結點       
    int j,k,t;       
    j=i;       
    while(parent[j] >0)  j=parent[j];//找根       
    k=i;       
    while(k!=j){//壓縮由i到根j的結點       
    t=parent[k];       
    parent[k]=j;       
    k=t;       
    }       
    return j;       
    }       
        
    void  UNION(int *parent,int i,int j)       
    {//使用加權規則合并根為i和j的兩個集合       
    int x;       
    x=parent[i]+parent[j];       
    if(parent[i] >parent[j]){//i的結點少       
    parent[i]=j;       
    parent[j]=x;       
    }       
    else{//j的結點少       
    parent[j]=i;       
    parent[i]=x;       
    }       
    }       
        
    int MIN(int  n,int  m)                                                                                                               
    {//求n和m的最小值       
    if(n >m)   return  m;       
    else return  n;       
    }       
    
	
	void Insertionsort(int  *D,int n)       
    {//將D中的元素按非增次序分類       
    int j,item,i;       
    D[0]=65525;       //設置監視      
    for(j=2;j <=n;j++){       
    item=D[j];       
    i=j-1;       
    while(item >D[i]){       
    D[i+1]=D[i];       
    i=i-1;       
    }       
    D[i+1]=item;             
    }           
    } 

    int  FJS(int *D,int n,int  b,int  *J,int *Q)       
    {//找J(n)的最優解，并返回最優解的個數       
    int i,*F,*p,j,l,m,k;       
    F=(int *)malloc((b+1)*sizeof(int));       
    p=(int *)malloc((b+1)*sizeof(int));       
   for(i=0;i <=b;i++){//將樹置初值       
    F[i]=i;       
    p[i]=-1;       
    }       
    k=0;//初始化J       
    for(i=1;i <=n;i++)       
    {//使用貪心規則       
    j=FIND(p,MIN(n,D[i]));       
    if(F[j]!=0)       
    {//選擇作業i       
    k=k+1;       
    J[k]=i;       
    Q[F[j]]=i;       
    m=F[j];       
    l=FIND(p,F[j]-1);       
    UNION(p,l,j);       
    F[j]=F[l];       
    }       
    }       
    return       k;//返回最優解的個數       
    }            
    int  MAXMUM(int   i,int  j)       
    {//求i和j的最大值       
    if(i >j)  return  i;       
    else   return j;       
    }       
        
    int MAX(int  *D,int i, int j)       
    {//D(1:n)是含有n個元素數組，求出D(i,j)中的最大值并返回       
    int  max,mid,max1,max2;       
    if(i==j)  max=D[i];       
    else       
    if(i==j-1)               
    if(D[i] <D[j]) max=D[j];       
    else   max=D[i];       
    else{       
    mid=(i+j)/2;       
    max1=MAX(D,i,mid);       
    max2=MAX(D,mid+1,j);       
    max=MAXMUM(max1,max2);       
    }       
    return max;       
    }