Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:终于AC了,采用跳跃式编码方式的同学看这里~~In Reply To:终于AC了,采用跳跃式编码方式的同学看这里~~ Posted by:heroskaka at 2015-03-26 15:40:25 > 拿到这个题目,第一反应是暴力,发现像素个数太大。。。然后发现只有前面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]; > } > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator