拿到这个题目，第一反应是暴力，发现像素个数太大。。。然后发现只有前面2行和最后两行才有变化，其他都是0，结果宽度也有可能很大。。。最后看了看大神的算法，采用跳跃式编码，就是说只在像素发生变化的位置进行编码，而像素没有变化的位置则其编码值与其左边的像素一致。仔细想一想，还是很好明白的，但是证明的话就。。。。采用这个方法，也有需要注意的地方。
1.在变化的点及周围8个点编码，第一个位置和最后一个位置也需要编码。
2.变化点及周围8个点，如果超出了第一个和最后一个范围可以忽略，但是超出了边界，右边超出的往下放，左边超出往上放，最后都是需要编码的。
最后附上代码~搞了2个晚上。。。WA了好几次。。。真不容易。。。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		List<String> output = new ArrayList<String>();
		String width = cin.nextLine();//获得列数
		while(!width.equals("0")){
			output.add(width);//别忘了把列数加入到输出中
			int wid = Integer.parseInt(width);
			String p = cin.nextLine();
			int[][] in = new int[2][1000];
			int pair = 0;
			int totalPixel = 0;
			while(!p.equals("0 0")){
				int pixel = Integer.parseInt(p.split(" ")[0]);//像素
				int number = Integer.parseInt(p.split(" ")[1]);//像素个数
				in[0][pair] = pixel;
				in[1][pair] = number;
				pair++;
				totalPixel += number;
				p = cin.nextLine();
			}
			int pos = 1;//标识当前的位置
			List<int[]> outputTemp = new ArrayList<int[]>();
			//这个地方要注意，起始点和终止点都需要进行编码
			for(int i=0;i<=pair;i++){
				//当前位置所处的行列
				int row = (pos-1)/wid;
				int col = (pos-1)%wid;
				for(int j=row-1;j<=row+1;j++){
					for(int k=col-1;k<=col+1;k++){
						int tempPos = j*wid + k + 1;
						//这个地方要注意，变化点及周围8个点，超出了也要编码
						if(tempPos < 1 || tempPos>totalPixel ){
							continue;
						}
						//获得转化后的像素值
						int[] temp = new int[]{tempPos,getMaxPixel(tempPos,in,wid,totalPixel)};
						outputTemp.add(temp);
					}
				}
				if(i < pair){
					pos += in[1][i];
				}
			}
			//快排，不多说
			quickSort(outputTemp);
			int temp = 0;
			//对临时数据进行合并
			for(int i=0;i<outputTemp.size();i++){
				if(outputTemp.get(temp)[1] == outputTemp.get(i)[1]){
					continue;
				}
				output.add(outputTemp.get(temp)[1]+" "+
						(outputTemp.get(i)[0] - outputTemp.get(temp)[0]));
				temp = i;
			}
			output.add(outputTemp.get(temp)[1]+" "+
					(totalPixel - outputTemp.get(temp)[0]+1));
			output.add("0 0");
			width = cin.nextLine();
		}
		output.add("0");
		cin.close();
		for(int i=0;i<output.size();i++){
			System.out.println(output.get(i));
		}
	}
	
	public static void quickSort(List<int[]> data){
		int length = data.size();
		quickSortRecursion(data,0,length-1);
	}
	//快排的递归
	public static void quickSortRecursion(List<int[]> data,int low,int high){
		if(low < high){
			int tempPos = data.get(low)[0];//基准数
			int tempPixel = data.get(low)[1];
			int i=low;
			int j=high;
			while(i < j){
				while(i < j && data.get(j)[0]
						>= tempPos){//先从右边开始，找到第一个比基准数小的
					j--;
				}
				data.set(i, data.get(j));//交换位置
				while(i < j && data.get(i)[0]
						<= tempPos){//再从左边开始，找到第一个比基准数大的
					i++;
				}
				data.set(j, data.get(i));//交换位置
			}//依次循环，直到基准数左边都比它小，右边都比它大
			data.set(i, new int[]{tempPos,tempPixel});
			quickSortRecursion(data,low,i-1);
			quickSortRecursion(data,i+1,high);
		}
	}

	public static int getMaxPixel(int pos,int[][] in,int wid,int totalPixel){
		int pixel = getPixelByPos(pos,in);
		int maxPixel = 0;
		
		int row = (pos-1)/wid;
		int col = (pos-1)%wid;
		for(int i=row-1;i<=row+1;i++){
			for(int j=col-1;j<=col+1;j++){
				int tempPos = i*wid + j + 1;
				if(i<0 || j<0 || j>=wid || tempPos>totalPixel || 
						tempPos == pos){
					continue;
				}
				int tempPixel = getPixelByPos(tempPos,in);
				if(maxPixel < Math.abs(tempPixel-pixel)){
					maxPixel = Math.abs(tempPixel-pixel);
				}
			}
		}
		return maxPixel;
	}
	
	public static int getPixelByPos(int pos,int[][] in){
		int i=0,j=0;
		while(i < pos){
			i += in[1][j++];
		}
		return in[0][j-1];
	}
}

• Re:终于AC了，采用跳跃式编码方式的同学看这里~~ (4072) zhrq 2018-02-05 09:17:16
• 求教：为什么最后一个位置要单独编码？ (324) zhrq 2018-02-05 09:34:22
  • Re:求教：为什么最后一个位置要单独编码？ (201) zhrq 2018-02-05 10:20:37