1.单行输入，且输入数据宽度很大 如
1000000
1 1000000
0 0
0
这种情况只需特殊考虑，因为标准测试数据只会以单行的形式来出现宽度很大的数据。
2.对于重复的数据，中间的size-2*width-2项都为0，可以不要计算。如：
10
5 5000000
3 5000000
0 0
0
代码：（新手，写的不是很精简- -）

import java.util.Scanner;

public class Main {
	private static int[] value;
	private static int[] length;
	private static int height;
	private static int width;
	public static void main(String[] args)
	{
		value = new int[1000];
		length = new int[1000];
		Scanner in = new Scanner(System.in);
		while(in.hasNext())
		{
			height = 0;
		    width = in.nextInt();
			if(width==0)
				break;
			int index =0;
			while(true)
			{
				int pixel = Integer.parseInt(in.next());
				int len = Integer.parseInt(in.next());
				if(pixel==0&&len==0)
					break;
				value[index] = pixel;
				length[index] = len;
				height += length[index];
				index ++;
			}
			height /= width;
			/*
			 * 考虑单行，并且测试数据很大的情况，如
			 * 10000000
			 * 4 10000000
			 * 0 0
			 * 0
			 */
			if(height == 1&&index ==1)
			{
				System.out.println(width);
				System.out.println(0+" "+height*width);
				System.out.println(0+" "+0);
			}
			else
			    detectAll();
		 }
		System.out.println(0);
	}
	private static int getValue(int index)
	{
		int sum = 0;
		int i = 0;
		while(sum <= index)
		{
			sum += length[i];
			i ++;
		}
		i--;
		return value[i];
	}
	private static int getLength(int index)
	{
		int sum = 0;
		int i = 0;
		while(sum <= index)
		{
			sum += length[i];
			i ++;
		}
		i--;
		return length[i];
	}
	private static int detect(int index)
	{
		int row = index / width;
		int col = index % width;
		int up=0,down=0,left=0,right=0,left_up=0,right_up=0,left_down=0,right_down=0;
		int val = getValue(index);
		if(row>0)
			up = Math.abs(getValue((row-1)*width+col)-val);
		if(row+1<height)
			down = Math.abs(getValue((row+1)*width+col)-val);
		if(col>0)
			left = Math.abs(getValue(row*width+col-1)-val);
		if(col+1<width)
			right = Math.abs(getValue(row*width+col+1)-val);
		if(row>0&&col>0)
			left_up = Math.abs(getValue((row-1)*width+col-1)-val);
		if(row>0&&col+1<width)
			right_up = Math.abs(getValue((row-1)*width+col+1)-val);
		if(row+1<height&&col>0)
			left_down = Math.abs(getValue((row+1)*width+col-1)-val);
		if(row+1<height&&col+1<width)
			right_down = Math.abs(getValue((row+1)*width+col+1)-val);
		int temp = Math.max(up, down);
		temp = Math.max(temp, left);
		temp = Math.max(temp, right);
		temp = Math.max(temp, left_up);
		temp = Math.max(temp, right_up);
		temp = Math.max(temp, left_down);
		temp = Math.max(temp, right_down);
		return temp;
	}
	/*
	 * 正常算法会导致运行超时
	 * 考虑如下情况：
	 * 11111
	 * 11111
	 * 11111
	 * 中间的一行可以不用计算。
	 */
	private static void detectAll()
	{
		System.out.println(width);
		int len = width * height;
		int i = 0;
		int sum = 1;
		int count = 0;
		while(i<len)
		{
			if(i == len-1)
			{
				System.out.println(detect(i)+" "+sum);
				i ++;
			}
			else if(getValue(i)==getValue(i+1)&&getLength(i)>2*width+4)
			{
				int size = getLength(i);
				if(count>width)
				{
					i += size - 2*width - 3;
					sum += size -2*width - 3;
					count = 0;
				}
				else if(detect(i)==detect(i+1))
				{
					i ++;
					sum ++;
					count ++;
				}
				else
				{
					System.out.println(detect(i)+" "+sum);
					i ++;
					sum = 1;
					count ++;
				}
				
			}
			else if(detect(i)==detect(i+1))
			{
				i ++;
				sum ++;
				count = 0;
			}
			else
			{
				System.out.println(detect(i)+" "+sum);
				i ++;
				sum = 1;
				count = 0;	
			}
		}
		System.out.println(0+" "+0);
	}
}

• Re:对于运行超时的两种情况做分析 附上java代码 (3959) suck_it 2013-05-14 16:45:08