> #include<stdio.h>
> #include<memory.h>
> #define MaxGoods  1100000
> #define MaxTrucks 1100000
> #define MaxBays   1100
> #define INFINITY  1000000000
> int truck[MaxTrucks];//卡车装的goods种类
> int cargo[MaxGoods];//货物所在heap的index
> int B,G,N;//B:bay's num; G:goods's kinds; N:truck's num
> int heapsize;
> struct timelist
> {
> 	int time;
> 	timelist *next;
> };
> timelist* head[MaxGoods];//每种货物被调用的时间队列头
> timelist* tail[MaxGoods];
> int       p;//池申请标志
> timelist  pool[MaxGoods];//池
> struct goods
> {
> 	int num;  //编号
> 	int time; //下次使用时间
>     int bay;  //所在bay
> }heap[MaxBays];
> 
> void rise(int index)
> {//index处具有新的time值,上浮操作
> 	int i=index;
> 	int value=heap[index].time;
> 	goods temp;
> 	while(1)
> 	{		
> 		if(i==0) break;
> 		if(value>=heap[(i-1)/2].time)//测试发现，次处改为> 竟然错的更大了，不解.
> 		{
> 			cargo[heap[i].num]=(i-1)/2;
> 			cargo[heap[(i-1)/2].num]=i;
> 			temp=heap[i];
> 			heap[i]=heap[(i-1)/2];			
> 			heap[(i-1)/2]=temp;	
> 			i=(i-1)/2;
> 		}
> 		else break;
> 	}
> }
> 
> void sink()
> {//堆顶下沉
> 	int i=0;
> 	goods temp;
> 	int value=heap[0].time;
> 	while(1)
> 	{
> 		if(i*2+1>=heapsize) break;
> 		if(value<heap[i*2+1].time)
> 		{
> 			cargo[heap[i].num]=i*2+1;
> 			cargo[heap[i*2+1].num]=i;
> 			temp=heap[i];
> 			heap[i]=heap[i*2+1];			
> 			heap[i*2+1]=temp;
> 			i=i*2+1;
> 			continue;
> 		}
> 		if(i*2+2>=heapsize) break;
> 		if(value<heap[i*2+2].time)
> 		{
> 			cargo[heap[i].num]=i*2+2;
> 			cargo[heap[i*2+2].num]=i;
> 			temp=heap[i];
> 			heap[i]=heap[i*2+2];			
> 			heap[i*2+2]=temp;					
> 			i=i*2+2;
> 		}
> 		else break;
> 	}
> }
> 
> int main()
> {
> //	freopen("in.txt","r",stdin);
> //	freopen("out.txt","w",stdout);
> 	int T;
> 	scanf("%d",&T);
> 	int casenum=1;
> 	while(casenum<=T)
> 	{
> 		// input part
> 
> 		scanf("%d%d%d",&B,&G,&N);
> 		printf("Case %d:\n",casenum++);
> 		int i;
> 		for(i=0;i<=G;i++)
> 		{
> 			cargo[i]=-1;//货物不在bay中
> 			tail[i]=NULL;
> 		}
> 		p=0;
> 		for(i=0;i<N;i++) 
> 		{
> 			scanf("%d",&truck[i]);
> 			pool[p].time=i;
> 			pool[p].next=NULL;
> 			if(tail[truck[i]]==NULL)
> 			{
> 				head[truck[i]]=&pool[p];
> 				head[truck[i]]->next=NULL;
> 				tail[truck[i]]=&pool[p++];
> 			}
> 			else
> 			{
> 				tail[truck[i]]->next=&pool[p];
>                 tail[truck[i]]=&pool[p++];
> 			}			
> 		}
> 
> 		//solve part
> 
> 		for(i=0;i<=G;i++) tail[i]=head[i];
> 		heapsize=0;
> 		int adjustvalue;//调整值
> 		for(i=0;i<N;i++)
> 		{	
> 			if(tail[truck[i]]->next==NULL) adjustvalue=INFINITY;
> 			else
> 			{
> 				adjustvalue=(tail[truck[i]]->next)->time;
> 				tail[truck[i]]=tail[truck[i]]->next;
> 			}
> 
> 			if(cargo[truck[i]]!=-1)
> 			{//货物已经在bay中
> 				
> 				heap[cargo[truck[i]]].time=adjustvalue;
> 				rise(cargo[truck[i]]);
> 				printf("NO ACTION\n");
> 				continue;
> 			}
> 			if(heapsize<B)
> 			{//bay还未占满,在堆中添加结点
> 				
> 				heap[heapsize].num=truck[i];
> 				heap[heapsize].bay=heapsize;
> 				heap[heapsize].time=adjustvalue;
> 				cargo[truck[i]]=heapsize++;
> 				rise(heapsize-1);
> 				printf("LOAD %d %d\n",heapsize,truck[i]);
> 				continue;
> 			}
> 			//需要置换 调整堆顶
> 			cargo[heap[0].num]=-1;
> 			heap[0].num=truck[i];
> 			heap[0].time=adjustvalue;
> 			cargo[truck[i]]=0;
> 			printf("LOAD %d %d\n",heap[0].bay+1,truck[i]);		
> 			sink();	
> 		}
> 		printf("\n");
> 	}
> 	return 1;
> }

• 呵呵，让你费心多不好意思，没做过的话还得从题目看起，看看做过的有没热心人帮下忙。 (0) Jayida 2004-10-24 13:51:29
  • 估计rruucc会帮你看一下，这个题目他写的spj呢^_^ (0) hawk 2004-10-24 13:52:28
    • 但愿是这样啦^_^ (0) Jayida 2004-10-24 13:53:34
      • 先做别的题吧，回头再看可能自己能有新发现呢 (0) hawk 2004-10-24 13:54:27
        • 哈哈，已经是第二次回头了。。。汗！ (0) Jayida 2004-10-24 13:56:21
    • 应该是atlas_of_rruucc吧？同一人？ (0) Jayida 2004-10-24 13:55:46
      • 就是指他，rruucc那个帐号是他以前的帐号 (0) hawk 2004-10-24 13:57:08
        • ^_^ 我们这不是侵犯了他的隐私权吗。。。 (0) Jayida 2004-10-24 13:59:45