0

我提交了关于 USACO 题为“The Clocks”的问题的代码。

这是问题的链接:http ://ace.delos.com/usacoprob2?a=wj7UqN4l7zk&S=clocks

这是输出:

正在编译...
编译:好的

正在执行...
   测试 1:测试正常 [0.173 秒,13928 KB]
   测试 2:测试正常 [0.130 秒,13928 KB]
   测试 3:测试正常 [0.583 秒,13928 KB]
   测试 4:测试正常 [0.965 秒,13928 KB]

  > 运行 5:执行错误:您的程序 (`clocks') 使用的次数超过
        分配的运行时间为 1 秒(它在 1.584 结束或停止
        秒)当出现测试用例 5 时。它使用了 13928 KB
        记忆。

        ------ 运行 5 的数据 ------
        6 12 12
        12 12 12
        12 12 12
        ----------------------------

        您的程序将数据打印到标准输出。这是数据:
        ------------------
        时间:_0.40928452
        ------------------

    测试 5:运行时 1.584>1 (13928 KB)

我编写了我的程序,以便它打印出程序在退出之前完成所花费的时间(以秒为单位)。

可以看出,退出前花了 0.40928452 秒。那么运行时间到底是怎么变成 1.584 秒的呢?我该怎么办?

如果有帮助,这是代码:

import java.io.*;<br>
import java.util.*;

class clocks {

    public static void main(String[] args) throws IOException {

        long start = System.nanoTime();
        // Use BufferedReader rather than RandomAccessFile; it's much faster
        BufferedReader f = new BufferedReader(new FileReader("clocks.in"));
        // input file name goes above
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("clocks.out")));
        // Use StringTokenizer vs. readLine/split -- lots faster

        int[] clock = new int[9];

        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(f.readLine());
            // Get line, break into tokens
            clock[i * 3] = Integer.parseInt(st.nextToken());
            clock[i * 3 + 1] = Integer.parseInt(st.nextToken());
            clock[i * 3 + 2] = Integer.parseInt(st.nextToken());
        }

        ArrayList validCombination = new ArrayList();;
        for (int i = 1; true; i++) {
            ArrayList combination = getPossibleCombinations(i);
            for (int j = 0; j < combination.size(); j++) {
                if (tryCombination(clock, (int[]) combination.get(j))) {
                    validCombination.add(combination.get(j));
                }
            }
            if (validCombination.size() > 0) {
                break;
            }
        }

        int [] min = (int[])validCombination.get(0);
        if (validCombination.size() > 1){
            String minS = "";
            for (int i=0; i<min.length; i++)
                minS += min[i];

            for (int i=1; i<validCombination.size(); i++){
                String tempS = "";
                int [] temp = (int[])validCombination.get(i);
                for (int j=0; j<temp.length; j++)
                    tempS += temp[j];
                if (tempS.compareTo(minS) < 0){
                    minS = tempS;
                    min = temp;
                }
            }
        }

        for (int i=0; i<min.length-1; i++)
            out.print(min[i] + " ");
        out.println(min[min.length-1]);

        out.close();                                  // close the output file

        long end = System.nanoTime();
        System.out.println("time: " + (end-start)/1000000000.0);
        System.exit(0);                               // don't omit this!
    }

    static boolean tryCombination(int[] clock, int[] steps) {
        int[] temp = Arrays.copyOf(clock, clock.length);

        for (int i = 0; i < steps.length; i++) 
            transform(temp, steps[i]);

        for (int i=0; i<temp.length; i++)
            if (temp[i] != 12)
                return false;
        return true;
    }

    static void transform(int[] clock, int n) {
        if (n == 1) {
            int[] clocksToChange = {0, 1, 3, 4};
            add3(clock, clocksToChange);
        } else if (n == 2) {
            int[] clocksToChange = {0, 1, 2};
            add3(clock, clocksToChange);
        } else if (n == 3) {
            int[] clocksToChange = {1, 2, 4, 5};
            add3(clock, clocksToChange);
        } else if (n == 4) {
            int[] clocksToChange = {0, 3, 6};
            add3(clock, clocksToChange);
        } else if (n == 5) {
            int[] clocksToChange = {1, 3, 4, 5, 7};
            add3(clock, clocksToChange);
        } else if (n == 6) {
            int[] clocksToChange = {2, 5, 8};
            add3(clock, clocksToChange);
        } else if (n == 7) {
            int[] clocksToChange = {3, 4, 6, 7};
            add3(clock, clocksToChange);
        } else if (n == 8) {
            int[] clocksToChange = {6, 7, 8};
            add3(clock, clocksToChange);
        } else if (n == 9) {
            int[] clocksToChange = {4, 5, 7, 8};
            add3(clock, clocksToChange);
        }
    }

    static void add3(int[] clock, int[] position) {
        for (int i = 0; i < position.length; i++) {
            if (clock[position[i]] != 12) {
                clock[position[i]] += 3;
            } else {
                clock[position[i]] = 3;
            }
        }
    }

    static ArrayList getPossibleCombinations(int size) {
        ArrayList l = new ArrayList();

        int[] current = new int[size];
        for (int i = 0; i < current.length; i++) {
            current[i] = 1;
        }

        int[] end = new int[size];
        for (int i = 0; i < end.length; i++) {
            end[i] = 9;
        }

        l.add(Arrays.copyOf(current, size));

        while (!Arrays.equals(current, end)) {
            incrementWithoutRepetition(current, current.length - 1);
            l.add(Arrays.copyOf(current, size));
        }

        int [][] combination = new int[l.size()][size];
        for (int i=0; i<l.size(); i++)
            combination[i] = (int[])l.get(i);

        return l;
    }

    static int incrementWithoutRepetition(int[] n, int index) {
        if (n[index] != 9) {
            n[index]++;
            return n[index];
        } else {
            n[index] = incrementWithoutRepetition(n, index - 1);
            return n[index];
        }
    }

    static void p(int[] n) {
        for (int i = 0; i < n.length; i++) {
            System.out.print(n[i] + " ");
        }
        System.out.println("");
    }
}
4

2 回答 2

1

也许他们用 Java 虚拟机启动/预热来计算整个运行时间

于 2010-06-17T07:58:59.077 回答
0

I have test your code. In my computer, it costs 6 seconds to calculate the sixth data. I also do a code for this problem, but I was failed at the sixth data. My solution costs 1.4 seconds. I don't know how to deal with it. Two possible cases to me is that my solution is not fast enough, or the solution code in Java can't run fast enough. So if you think your solution is fast enough, I suggest you to code it in C++ or C.

Good luck with you.

I just fond a better solution on topcoder this is the URL: enter link description here

于 2011-03-07T15:42:55.960 回答