#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;
}

• 这个太长了，输入也太长了，现在没法帮你看 (3467) hawk 2004-10-24 13:44:16
  • 呵呵，让你费心多不好意思，没做过的话还得从题目看起，看看做过的有没热心人帮下忙。 (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