我提交了关于 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("");
}
}