#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct mode
{
	int x;
    int y,a,b;
}data;
typedef struct node
{
	int x;
	int y;
}re;
static int line;
int max(data* d,int s);
void write(data* d);
void compute(data* d,re* r,int line);
void print(re* r,int line);
int main(void)
{
	extern int line;
	data d[255];
	re r[255];
	while(scanf("%d",&line) && line != 0)
	{
		write(d);
		compute(d,r,line);
		print(r,line);
	}
	printf("0\n");
	return 0;
}

void write(data* d)
{
	int i,s=0;
	int num;
	int time;
	for(i=0;i<255;i++)
	d[i].y=0;
	i=0;
	while(scanf("%d %ld",&num,&time) && (num!=0||time!=0))
	{
		d[i].x=num;
		d[i].y=time;
		d[i].a=s;
		s+=time;
		d[i].b=s;
		i++;
	}
}

void compute(data* d,re* r,int line)
{
	int i,j=0;
	int s;
	for(i=0;i<255;i++)
	r[i].y=0;
 	for(i=0;d[i].y!=0;i++)
	{
		for(s=d[i].a;s<d[i].b&&s<d[i].a+line+2;s++)
		{
			if(s==0)
			{
				r[j].x=max(d,s);
				r[j].y=1;
			}
			else
			{
				if(r[j].x==max(d,s))
				r[j].y++;
				else
				{
					j++;
					r[j].x=max(d,s);
					r[j].y=1;
				}
			}
		}
		if(s!=d[i].b)
		{
			if(d[i].y-2*line-2>0)
			{
				if(r[j].x==0)
				r[j].y+=d[i].y-2*line-2;
				else 
				{
					j++;
					r[j].x=0;
					r[j].y=d[i].y-2*line-2;
				}
				s+=d[i].y-2*line-2;
			}
			for(;s<d[i].b;s++)
			{
				if(r[j].x==max(d,s))
				r[j].y++;
				else
				{
					j++;
					r[j].x=max(d,s);
					r[j].y=1;
				}
			}
		}
	}
}

int max(data* d,int s)
{
	extern int line;
	int i,j;
	int der[8];
	int res[8],m;
	int ma,S;
	der[0]=-1;
	der[1]=1;
	der[2]=-1*line;
	der[3]=line;
	der[4]=-1*line-1;
	der[5]=-1*line+1;
	der[6]=line-1;
	der[7]=line+1;
	for(i=0;i<255;i++)
	{
		if(d[i].y==0)
		break;
	}
	S=d[i-1].b;
	for(i=0;i<255;i++)
	if(d[i].a<=s&&d[i].b>s)
	break;
	m=d[i].x;
	ma=-1;
	for(i=0;i<8;i++)
	{
		if(s+der[i]>=0 && s+der[i]<S)
		{
			for(j=0;j<255;j++)
			if(d[j].a<=s+der[i]&&d[j].b>s+der[i])
			break;
			res[i]=fabs(m-d[j].x);
			switch(i)
			{
				case 0:
				case 4:
				case 6:if(s%line==0) res[i]=-1;break;
				case 1:
				case 5:
				case 7:if((s+1)%line==0) res[i]=-1;break;
			}
		}
		else 
			res[i]=-1;
		if(ma<res[i])
			ma=res[i];
	}
/*=res[0];
	for(i=0;i<8;i++)
	if(ma<res[i])
	ma=res[i];*/
	return ma;
}

void print(re* r,int line)
{
	int i;
	printf("%d\n",line);
	for(i=0;i<255;i++)
	{
		if(r[i].y==0)
		break;
		printf("%d %ld\n",r[i].x,r[i].y);
	}
	printf("0 0\n");
}

• Re:修改提交N次了，还是超时，晒代码，请大虾指教： (386) 102103105 2011-10-01 14:15:14
  • Re:修改提交N次了，还是超时，晒代码，请大虾指教： (418) zhangyufei 2011-10-11 22:05:56
    • Re:修改提交N次了，还是超时，晒代码，请大虾指教： (30) zhangyufei 2011-10-11 22:07:02