天天看点

九度OJ-1005 Graduate Admission

今天做了一下这个题,但就是没有AC成功,还一堆问题:MLE,OLE,关键释放了内存反而报MLE。。。。。。。。
           
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

static int N;//申请数目
static int M;//学校数目
static int K;//可填志愿数

typedef struct School{
	int m_quota;//名额
	int *m_stu;//接收学生编号
	int m_count;//当前招生数
}School;

typedef struct Applicant{
	int m_num;//申请编号
	int m_GE;
	int m_GI;
	double m_Final;
	int m_Rank;//等级
	int* m_choice;//志愿
}Applicant;



School* initial()
{
	int i = 0;
	School* schools;
	scanf("%d %d %d",&N,&M,&K);
	schools = (School*)malloc(M * sizeof(School));

	while (i < M)
	{
		scanf("%d",&(schools[i].m_quota));
		schools[i].m_stu = (int *)malloc(10 * schools[i].m_quota * sizeof(int));
		schools[i].m_count = 0;

		++i;
	}

	return schools;
}

Applicant* getApplicants()
{
	int i = 0;
	int j = 0;
	Applicant* app = (Applicant*)malloc(N * sizeof(Applicant));

	while(i < N)
	{
         (app[i]).m_choice = (int*)malloc(K * sizeof(int));
		 scanf("%d",&(app[i].m_GE) );
		 scanf("%d",&(app[i].m_GI) );
		 app[i].m_Final = ((app[i].m_GE + app[i].m_GI) / 2.0);
		 app[i].m_num = i;

		 while (j < K)
		 {
			 scanf("%d",&((app[i]).m_choice)[j] );
			 ++j;
		 }

		 j = 0;
		 ++i;
	}

	return app;
}

void SWAP(Applicant *a, Applicant *b)
{
	int tmp_num;//申请编号
	int tmp_GE;
	int tmp_GI;
	double tmp_Final;
	int tmp_Rank;//等级
	int* tmp_choice;//志愿

	tmp_choice = a->m_choice;
	tmp_Final  = a->m_Final;
	tmp_GE     = a->m_GE;
	tmp_GI     = a->m_GI;
	tmp_num    = a->m_num;
	tmp_Rank   = a->m_Rank;

	a->m_choice = b->m_choice;
	a->m_Final  = b->m_Final;
	a->m_GE     = b->m_GE;
	a->m_GI     = b->m_GI;
	a->m_num    = b->m_num;
	a->m_Rank   = b->m_Rank;

	b->m_choice = tmp_choice;
	b->m_Final 	= tmp_Final;
	b->m_GE    	= tmp_GE;
	b->m_GI    	= tmp_GI;
	b->m_num   	= tmp_num;
	b->m_Rank  	= tmp_Rank;


}
//void printG(Applicant *app)
//{
//	int i;
//
//	for (i = 0; i < N; ++i)
//	{
//		printf("i:%d num:%d final:%f ge:%d\n",i,app[i].m_num,app[i].m_Final,app[i].m_GE);
//	}
//}
void getRank(Applicant* app)
{
	int i,j,k;
	int max_ge,index,index_2;
	double max_final;

	for (i = 0; i < N-1; ++i)
	{
		max_final = app[i].m_Final;
		max_ge = app[i].m_GE;
		index = i;//记录当前最大的final的下标
		for (j = i + 1; j < N; ++j)
		{
			if (max_final < app[j].m_Final)//找到比它大的,记录其final,下标,并替换index,
			{
				max_final = app[j].m_Final;
				max_ge    = app[j].m_GE;
				index = j;
			}
		}//找到最大的final,和对应的下标index,

		if (index != i)//把当前final最大的元素放到第 i 位
			SWAP(app + index, app + i);

		//查找final相同时,ge的最大,放到元首
		index_2 = i;//假定当前坐标下就是最大的位置
		for (k = i + 1; k < N; ++k)
		{
			if (max_final == app[k].m_Final)
			{
				if (max_ge < app[k].m_GE)//找到一个更大的GE
				{
					max_ge = app[k].m_GE;
					index_2 = k;//记录在final相同时,ge最大的下标

				}
			}
		}

		//比较在final相同时,ge最大位置是不是当前final记录的最大位置
		if (index_2 != i)
			SWAP(app + i, app + index_2);	
	}
	/*printf("分配等级前:\n");
	printG(app);*/


	//等级分配
	app[0].m_Rank = 1;
	for (i = 1; i < N ; ++i)
	{
		if (app[i].m_Final < app[i-1].m_Final)//如果当前的元素final比上一个小,则其等级比上一个小,+1
			app[i].m_Rank = app[i-1].m_Rank + 1;
		else//如果final相同,则比较ge
		{
			if (app[i].m_GE == app[i-1].m_GE)//如果相同,则同等级别
				app[i].m_Rank = app[i-1].m_Rank;
			else
				app[i].m_Rank = app[i-1].m_Rank + 1;//否则,加一
		}
		
	}
}

//void printRank(Applicant* app)
//{
//	int i;
//
//	for (i = 0; i < N; ++i)
//	{
//		printf("num:%d rank:%d\n",app[i].m_num,app[i].m_Rank);
//	}
//}

void start_task(Applicant *app,School *schools)
{
	int i,j,k,flag=0;
	int choice;
	int tmp;
	int rank;

	for (i = 0; i < N; ++i)//扫描所有申请
	{
		for (j = 0; j < K; ++j)//扫描每个申请的志愿
		{
			choice = ((app[i]).m_choice)[j];//取出志愿学校

			if (0 == (schools[choice]).m_count)//如果当前申请的学校还没有人申请,则直接被录取
			{
				( (schools[choice]).m_stu )[((schools[choice]).m_count)] = (app[i]).m_num;//记录当前学生的编号到学校录取中
				(schools[choice]).m_count++;
				break;//当前学生被录取,所以,扫描下一个申请

			}
			else//已有人申请
			{
				//取出当前学校中最后一个被录取的申请编号
				tmp = ((schools[choice]).m_stu)[((schools[choice]).m_count) - 1];
				//根据这个编号找出这个申请的等级
				for (k = 0; k < N; ++k)
				{
					if (tmp == app[k].m_num)
					{
						rank = app[k].m_Rank;
						break;
					}
				}

				if (rank == app[i].m_Rank)//比较等级,如果等级相同,直接录取
				{
					((schools[choice]).m_stu)[((schools[choice]).m_count)] = (app[i]).m_num;//记录当前学生的编号到学校录取中
					(schools[choice]).m_count++;
					break;//当前学生被录取,所以,扫描下一个申请
				}//否则查看学校是否还有名额,没有就扫描下一个志愿
				else 
				{
					if ((schools[choice]).m_count < (schools[choice]).m_quota)//说明这个学校没招满人
					{
						( (schools[choice]).m_stu )[((schools[choice]).m_count)] = (app[i]).m_num;//记录当前学生的编号到学校录取中
						(schools[choice]).m_count++;
						break;//当前学生被录取,所以,扫描下一个申请
					}//否则,进入下一个志愿的rvqa
				}
			}
		}
	}
}

void _swap_(int* a, int *b)
{
	int temp;
	temp = *a;
	*a   = *b;
	*b   = temp;
}

void sortUp(School* sch)
{
	int i,j,k;
	int index,min;
	int tmp;
	for (i = 0; i < M; ++i)
	{
		for (j = 0; j < sch[i].m_count; ++j)
		{
			index = j;
			min = ((sch[i]).m_stu)[j];
			for (k = j+1; k < sch[i].m_count; ++k)
			{
				if (min > ((sch[i]).m_stu)[k])
				{
					min = ((sch[i]).m_stu)[k];
					index = k;
				}
			}

			if (index != j)
			{
				_swap_( (sch[i]).m_stu + index, (sch[i]).m_stu + j );
			}
		}
	}
}

void printsch(School* sch)
{
	int i,j;
	int count;
	int index,min;

	for (i = 0; i < M; ++i)
	{
	    count = sch[i].m_count;
		if (count > 0)
		{
			for (j = 0; j < count; ++j)
			{
				printf("%d",((sch[i]).m_stu)[j]);
				if (j < count-1 )
					printf("%c",' ');
			}
			printf("\n");
		}
		else
		{
           printf("\n");
		}
			
		
	}
}

void freeall(Applicant *app, School *sch)
{
	int i,j;

	for (i = 0; i < N; ++i)
	{
		free((app[i]).m_choice);
	}

	for (j = 0; j < M; ++j)
	{
		free((sch[j]).m_stu);
	}

	free(app);
	free(sch);
}

int main(int argc, char* argv[])
{
	School *schools;
    Applicant *app;

	while(1)
	{
		schools = initial();
		app = getApplicants();
		getRank(app);
		start_task(app, schools);
		sortUp(schools);
		printsch(schools);
		freeall(app, schools);
	}


	//printf("rank:\n");
	//printRank(app);
	//getch();

	return 0;
}
           

VS中测试过数据,没有问题,但又不是WA,而是OLE......

Mian中添加freeall()释放空间后,反而报MLE错误,内存占273224KB 但去了这个函数后,反而只占1KB左右的内存,实在是不解,

去掉freeall()函数后,又报另一个错误OLE!!!!!真不知为什么。。。。。。。。。