#include<iostream>
using namespace std;
int a[1000][2];
int get_num(int i,int m)
{
	int s=0;
	for(int j=0;j<m;j++)
	{
		s+=a[j][1];
		if(s>=i)
			break;
	}
	return a[j][0];
}

int get_max(int m,int i,int width)
{
	int s,s1,s2;
	s1=get_num(i,m);
	if((i-(width+1))>0&&(i-1)%width!=0)
	{
		s=get_num(i-(width+1),m)-s1;
		s=s>0?s:(-s);
	}
	if((i-width)>0)
	{
		s2=get_num(i-width,m)-s1;
		s2=s2>0?s2:(-s2);
		s=s>s2?s:s2;
	}
	if((i-width+1)>0&&i%width!=0)
	{
		s2=get_num(i-width+1,m)-s1;
		s2=s2>0?s2:(-s2);
		s=s>s2?s:s2;
	}
	if((i-1)>0&&(i-1)%width!=0)
	{
		s2=get_num(i-1,m)-s1;
		s2=s2>0?s2:(-s2);
		s=s>s2?s:s2;
	}
	if((i+1)<=m&&i%width!=0)
	{
		s2=get_num(i+1,m)-s1;
		s2=s2>0?s2:(-s2);
		s=s>s2?s:s2;
	}
	if((i+width-1)<=m&&(i-1)%width!=0)
	{
		s2=get_num(i+width-1,m)-s1;
		s2=s2>0?s2:(-s2);
		s=s>s2?s:s2;
	}
	if((i+width)<=m)
	{
		s2=get_num(i+width,m)-s1;
		s2=s2>0?s2:(-s2);
		s=s>s2?s:s2;
	}
	if((i+width+1)<=m&&i%width!=0)
	{
		s2=get_num(i+width+1,m)-s1;
		s2=s2>0?s2:(-s2);
		s=s>s2?s:s2;
	}
	return s;
}

int main()
{
	int width;
	int i,j,m;
	int s,k=0;
	while(1)
	{
		cin>>width;
		m=0;
		if(width==0)
			break;
		j=0;
		while(1)
		{
			cin>>a[j][0]>>a[j][1];
			m+=a[j][1];
			if(!a[j][0]&&!a[j][1])
				break;
			j++;
		}
		cout<<width<<endl;
		i=1;
		k=1;
		s=get_max(m,i,width);
		while(1)
		{
			i++;
			if(i<=m+1)
			{
				if(s==get_max(m,i,width))
					k++;
				else 
				{
					cout<<s<<" "<<k<<endl;
					k=1;
					s=get_max(m,i,width);
				}
			}
			else 
				break;
		}
		cout<<0<<" "<<0<<endl;
	}
	cout<<0<<endl;
	return 0;
}

• Re:超时啊，还有什么好的算法啊 (20) candy_102092 2007-02-08 20:10:10