a1.cpp

第二届全国高校 BBS 程序开发大赛算法组

#include <iostream>
#include <list>
using namespace std;
#include <memory.h>

void outputTeam(list<int> *team, int R);
int findQuickTeam(int *length, int R);
int getTotalTime(list<int> *team,int R);
int getMaxTime(int *length, int R);

void main()
{
	//数据输入
	int N,R,temp,curteam;
	list<int> *team,T;
	cout<<"Input the numbers:"<<endl;
	cin>>N>>R;
	team = new list<int> [R];
	for (int i = 0; i<N; ++i){
		cin>>temp;
		T.push_back(temp);
	}		

	/**************************计算总时间花费最少的队列分布并输出***************************
	             算法原理：各队伍最外层人的等待时间之和必然为所有人T值的总和Ttotal，
				 而内部某层人的等待时间之和为Ttotal减去外层各元素T值的加合，因此当前
				 未排队人中T值最大的人就要排在当前所处层数最浅的位置（由外向内排）
	***************************************************************************************/
	T.sort(); 
	curteam=0;
	list<int>::reverse_iterator riter = T.rbegin();
	while (riter!=T.rend()){
		team[curteam].push_front(*riter);
		++riter;
		curteam = (curteam==R-1) ? 0 : (curteam+1);
	}
	cout<<"Team allocation costing the least time in total : "<<endl;
	cout<<"Time: "<<getTotalTime(team,R)<<endl;
	outputTeam(team,R);	

	/**************************计算打水时间最短的队列分布并输出*****************************
	              算法原理：本问题为NP问题，采用Greedy Method加上局部优化找出其近似最优解
				  具体方法：将排队者按打水时间T排序，然后逆序插入当前某一个队列的队首
				  插入准则：选择当前总耗时最短的队列进行插入。当所有队列中人数总和为1或者
				  当前每一个队列都仅有一个人（即刚刚出现各队列耗时都不为0的情况）时，穷举
				  当前需插入的排队者对最终打水时间的影响，选择使得最终打水时间为最短的插入
				  方式。
				  注明：本算法输出结果为近似最优解，即未必是时间最短的序列分布，但其耗时与
				  最短耗时已经相当接近
	***************************************************************************************/
	int index,*length = new int[R],j=0;                 //纪录各队列当前总耗时
	memset((void*)length, 0, sizeof(int)*R);
	riter = T.rbegin();
	bool sign=false;                                    //标志穷举是否已经发生
	while (riter!=T.rend()){
		index = findQuickTeam(length,R);

		//局部优化：当当前所有队列人数总和为1或者每支队伍都刚刚非空时，
		//对此插入者的插入方式(2种或R种)进行穷举，取最优解
		if ((length[index]!=0 && (!sign)) || (j==1))
		{
			int minlength,minindex;
			int tempR = ((j==1) && (R>1)) ? 2 : R;
			for (i=0; i<tempR; ++i)
			{
				list<int>::reverse_iterator newriter=riter;
				int *newlength=new int[R];
				memcpy((void *)newlength, (void *)length, sizeof(int)*R);
				newlength[i]+=*newriter;
				++newriter;
				while (newriter!=T.rend()){
					newlength[findQuickTeam(newlength,R)]+=*newriter;
					++newriter;
				}
				if (i==0){
					minlength = getMaxTime(newlength,R); 
					minindex  = 0;
				}
				else if (minlength > (temp=getMaxTime(newlength,R))){
					minlength = temp;
					minindex  = i;
				}
				delete [] newlength;   //回收内存
			}
			index = minindex;
			sign  = true;
		}
		/***********************************************************************/

		team[index].push_front(*riter);
		length[index]+=*riter;
		++riter;
		++j;
	}
	cout<<endl<<"Team allocation costing the least time on average : "<<endl;
	cout<<"Time: "<<getMaxTime(length,R)<<endl;
	outputTeam(team,R);	

	//回收内存
	T.clear();
	delete [] team;
}

//输出各队列，同时清空各队列内容
void outputTeam(list<int> *team, int R)
{
	for (int i = 0; i<R; ++i){
		cout<<"Team "<<i<<" : ";
		while (!team[i].empty()){
			cout<<team[i].front()<<"  ";
			team[i].pop_front();
		}
		cout<<endl;
	}
}

//找出当前耗时最短的队列
inline int findQuickTeam(int *length, int R)
{
	int result = length[0],index=0;
	for (int i = 0; i<R; ++i){
		if (result > length[i]){
			result = length[i]; 
			index=i;
		}
		if (!result)
			return index;
	}
	return index;
}

//找出所有人耗时总和
inline int getTotalTime(list<int> *team,int R)
{
	int totaltime=0,curtime=0;
	for (int i = 0; i<R; ++i){
		curtime=0;
		if (!team[i].empty())
		{
			list<int>::iterator iter=team[i].begin();
    		while (iter!=team[i].end()){
    			curtime+=*iter;
				totaltime+=curtime;
				++iter;
			}
		}
	}
	return totaltime;
}

//找出当前耗时最长队列的耗时
inline int getMaxTime(int *length, int R)
{
	int result = length[0];
	for (int i=0; i<R; ++i)
		result = (result < length[i]) ? length[i] : result;
	return result;
}