#include <stdio.h>
#include <malloc.h>
#define     MAXTASK		100
#define		MAXMACH		100
#define		LT(A,B)  ((A) < (B))
#define		EQ(A,B)  ((A) == (B))
#define		LQ(A,B)  ((A) <= (B)) 
#define		GT(A,B)	 ((A) >  (B))

typedef	struct{        //任務所需時間
	int ti;
	int num;
}TaskType;

typedef struct{			//分配給機器的時刻
	int sch;
	int num;
}MachType;

typedef	struct{			//任務的數據結構
	int		tasknum;
	TaskType	*task;
}HeapType;

typedef struct{			//機器的數據結構
	int		machnum;
	MachType	*machine;
}BitType;


void HeapAdjust (HeapType &H,int s,int m){
//已經H.task[s..m]中記錄的時間除H.task[s].ti之外均滿足堆的定義,本函數調整H.task[s]
//的時間,使H.task[s..m]成為一個大頂堆
	TaskType rc;
	int	j;
	rc=H.task[s];
	for(j=2*s; j<=m; j*=2){//沿ti較大的孩子結點向下篩選
		if( j<m && LT(H.task[j].ti,H.task[j+1].ti) )	++j;//j為ti較大的記錄的下標
		if( !LT(rc.ti,H.task[j].ti) )	break;				//rc應插入在位置s上
		H.task[s]=H.task[j];
		s=j;
	}
	H.task[s]=rc;     //插入
}

void BitAdjust (BitType &B,int s,int m){
	//已經B.machine[s..m]中記錄的時間除B.machine[s].sch之外均滿足堆的定義,本函數調整B.machine[s]
	//的時間,使B.machine[s..m]成為一個小頂堆
	MachType rc;
	int j;
	rc=B.machine[s];
	for(j=2*s;j<=m;j*=2){//沿sch較小的孩子結點向下篩選
		if(j<m && GT(B.machine[j].sch , B.machine[j+1].sch))  ++j;
		if(LT(rc.sch, B.machine[j].sch))	break;
		B.machine[s]=B.machine[j];
		s=j;
	}
	B.machine[s]=rc;
}
void Heap(BitType &B,int s,int m){
	MachType rc;
	int	j;
	rc=B.machine[s];
	for(j=2*s; j<=m; j*=2){//沿ti較大的孩子結點向下篩選
		if( j<m && LT(B.machine[j].sch,B.machine[j+1].sch) )	++j;//j為ti較大的記錄的下標
		if( !LT(rc.sch,B.machine[j].sch) )	break;				//rc應插入在位置s上
		B.machine[s]=B.machine[j];
		s=j;
	}
	B.machine[s]=rc;     //插入
}

void HeapSort( HeapType &H){
	int i;
	for( i=H.tasknum/2 ; i>0 ; --i) //把H.task[1..H.tasknum]建成大頂堆
		HeapAdjust(H,i,H.tasknum);
}
void BitSort( BitType &B){
	int i;
	for(i=B.machnum/2 ;i>0 ; --i)  //把B.task[1..B.tasknum]建成小頂堆
		BitAdjust(B,i,B.machnum);
}

int	LPT(HeapType &H,BitType &B){
//任務調度算法
	int i,j;
	int machine[MAXTASK][MAXMACH];//machine[i]為第i臺機器被分配的任務
	for(i=0;i<=B.machnum;i++)     //初始化數組machine
		for(j=0;j<=H.tasknum;j++)
			machine[i][j]=0;
	if(H.tasknum <= B.machnum){
	//作業數n<=機器數m,則將作業i分配到機器i上
	//最短調度長度等于n個作業中處理時間最大值
		for(i=1;i<=H.tasknum;i++){
			B.machine[i].sch=H.task[i].ti;
			machine[i][0]=H.task[i].num;
		}
		B.machine[0].sch=B.machine[1].sch;
		for(i=2;i<=H.tasknum;i++){// 查找其中的最大值
			if(GT(B.machine[i].sch,B.machine[0].sch))
				B.machine[0].sch=B.machine[i].sch;
		}
		B.machine[1].sch=B.machine[0].sch;
	}
	else {
		for(i=H.tasknum;i>=1;--i){//分配任務
			HeapSort(H);//把任務按時間排成大頂堆
			BitSort(B); //把機器按時刻表排成小頂堆
			B.machine[1].sch=B.machine[1].sch+H.task[1].ti;//將H的堆頂任務分配給B的堆頂機器
			for(j=0;machine[B.machine[1].num][j];j++) ;
			machine[B.machine[1].num][j]=H.task[1].num;
			H.task[1]=H.task[i];//把排在最后的任務置堆頂(即把堆頂任務刪除)
			H.task[i].ti=0;
			H.tasknum--;//任務數少一
		}
		for(i=B.machnum/2;i>=1;i--)//任務全部分配完時,再一次大頂堆排序
			Heap(B,i,B.machnum);
	}
	printf("scheme dispather:\n");
	printf("machine\t\ttask\n");
	for(i=1;i<=B.machnum && machine[i][0];i++){
		printf("NO.%d:   \t",i);
		for(j=0;machine[i][j];j++)
			printf("%d  ",machine[i][j]);
		printf("\n");
	}
	return B.machine[1].sch;
}

void main(){
	HeapType H;
	BitType  B;
	printf("input the amount of machines:");
	scanf("%d",&B.machnum);
	fflush(stdin);
	B.machine=(MachType *)malloc((B.machnum+1) * sizeof(MachType));
	for(int i=1;i<=B.machnum;i++){
		B.machine[i].sch=0; //初始化機器的時刻
		B.machine[i].num=i;
	}
	printf("input the amount of tasks:");
	scanf("%d",&H.tasknum);
	fflush(stdin);
	H.task=(TaskType *)malloc((H.tasknum+1)*sizeof(TaskType));
	for(i=1;i<=H.tasknum;i++){
		H.task[i].num=i;
		printf("NO.%d task:",i);
		scanf("%d",&H.task[i].ti);
	}
	printf("\n");
	printf("the least time of the job scheduling:%d\n",LPT(H,B));
	fflush(stdin);
	getchar();
}