poj1009

2014-05-24

题目

网址：

http://poj.org/problem?id=1009

参考网站：

http://blog.csdn.net/rongyongfeikai2/article/details/7182098

代码及其详细注释

import java.io.*;
import java.math.*;
import java.util.*;

/* 用来记录数据的类。
 * 1.记录输入数据的数值和长度
 * 2.记录输出数据的位置和值
 * 变量名没取好，见谅*/
class Record{
    private int number;
    private int count;

    public Record(int number, int count){
        this.number = number;
        this.count = count;
    }
    public int getNum(){
        return number;
    }
    public int getCount(){
        return count;
    }
    public String toString(){
        return number +" "+count;
    }
}
/* 实现比较接口的类
 * 用来给输出数据按照位置的大小排序*/
class RecordComparator implements Comparator{
    public int compare(Object o1, Object o2){
        Record r1 = (Record)o1;
        Record r2 = (Record)o2;
        if(r1.getNum() > r2.getNum())
            return 1;
        else if(r1.getNum() == r2.getNum())
            return 0;
        else
            return -1;
    }
}

public class Main{

    private static int width = 0; // 数据宽度
    private static int Num = 0;   // 记录数据的总的个数
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
        Main main = new Main();
        while(true){
            line = in.readLine();
            if("0".equals(line)){
                System.out.println("0");  // 打印结束标志
                break;
            }
            width = Integer.parseInt(line);
            System.out.println(width);
            ArrayList pairs = new ArrayList();     // 输入数据，放在arraylist中
            ArrayList outPairs = new ArrayList();  // 输出数据
            int pos = 1; // 起始位置，每轮从1开始
            Num = 0;     // 起始个数为0
            //读入每一轮的数据到pairs，并计算出总数据的个数
            while(true){
                line = in.readLine();
                if("0 0".equals(line))
                    break;
                String[] data = line.split(" ");
                int number = Integer.parseInt(data[0]);
                int count = Integer.parseInt(data[1]);
                Record r = new Record(number, count);
                pairs.add(r);
                Num += r.getCount();
            }
            //只读取改变了的那些值的输出值，并计算被它所影响的那些数据的输出值
            for(int i = 0;i <= pairs.size(); i++){
                
                // 将位置换算成行和列，从0开始
                int row = (pos - 1) / width;
                int col = (pos - 1) % width;
                //计算元素在最后一列，且该元素下两行还有数据的那些的数值，因为这些值如有改变的话，会影响它的下两行的第一个值的输出值
                if(col == width -1){
                    if((row + 2) * width < Num){
                        Record rd = new Record(pos + width + 1, main.calNode(pairs, pos + width + 1, row + 2, 0));
                        outPairs.add(rd);
                    }
                }
                //计算改变了的数据的值及其受它所影响的值的输出值
                for(int m = row - 1; m <= row + 1; m++){
                    for(int n = col - 1; n <= col + 1; n++){
                        int myPos = m * width + n +1;
                        if((m >= 0)&&(n >= 0)&&(n < width)&&(myPos <= Num)){ //  关键判断
                            Record rd = new Record(myPos, main.calNode(pairs, myPos, m, n));
                            outPairs.add(rd);
                        }
                    }
                }
                // 计算出下一个值改变了的数据
                if(pairs.size() != i){
                    pos += pairs.get(i).getCount();
                }
            }
            //给输出数据按照位置大小，从小到大排序，以便输出
            Collections.sort(outPairs, new RecordComparator());
            //输出结果数据。注意最后一批数据
            int cur = 0;
            for(int i = 0; i < outPairs.size(); i++){
                if(outPairs.get(i).getCount() == outPairs.get(cur).getCount()){
                    continue;
                }
                System.out.println(outPairs.get(cur).getCount()+" "+(outPairs.get(i).getNum() - outPairs.get(cur).getNum()));
                cur = i;
            }
            System.out.println(outPairs.get(cur).getCount()+" "+(Num - outPairs.get(cur).getNum() + 1)); //打印该轮的最后一批数据
            System.out.println("0 0");  // 打印该轮结束标志
        }
    }
    /**计算该数据的输出值，参数是数据的行和列，以及它所在的位置**/
    public  int calNode(ArrayList pairs, int pos, int row, int col){
        int result = 0;
        for(int i = row - 1; i <= row + 1; i++){
            for(int j = col -1; j <= col + 1; j++){
                int tempPos = i * width + j + 1; // 要和该位置数据比较的其他元素的位置
                if(pos == tempPos){
                    continue;
                }
                if(i>=0&&j>=0&&j<width&&tempPos<=Num){ //关键判断
                    int value = Math.abs(getValue(pairs, tempPos) - getValue(pairs, pos));
                    if(result < value)
                        result = value;
                }
            }
        }
        return result;
    }
    /** 给定一个位置，得到该位置处的数据的信息。如，数值和长度信息 **/
    public  int getValue(ArrayList pairs, int pos){
        
        int i = 0, j = 0;
        for(i = 0; j < pos; i++){
            j += pairs.get(i).getCount();
        }
        return pairs.get(i - 1).getNum();
    }
}


</pre>

**总结**

 * 不需要弄两个二维数组存放输入输出数据，直接用2个list搞定，节省了内存开销。
 * 用一个记录位置信息的变量，来换算出每个数据的坐标（行和列）。
 * 添加类的比较器，用一个类去实现Comparator类，以及其int compare()方法;然后调用Collections的sort()方法，打到快速排序的效果。
 * 计算每个点的输出值的时候，采用3行3列的方法，并在其中添加关键判断来过滤掉不应该有的值。
 * 收获多多啊。