Closed. This question is off-topic。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗? Update the question,所以它是on-topic,用于堆栈溢出。
                        
                        5年前关闭。
                                                                                            
                
        
我确信这里有很多人对Codeforce问题感兴趣,所以这里是问题:

问题:我坚持解决one of Codeforces problems。我在第21次测试中得到Time limit exceeded。我找到了solition,但它似乎比我的慢。

考虑了一段时间后,我决定用Java 7写一个更快的解决方案是不可能的。

问题:是否可以用Java 7编写更快的解决方案?

我的解决方案:

public class PolicePatrol {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int criminalAmount = in.nextInt();
        int patrolCarCapacity = in.nextInt();
        int[] criminalLocations = new int[criminalAmount];
        for (int i = 0; i < criminalLocations.length; i++)
            criminalLocations[i] = in.nextInt();

        long distance = calcDistance(criminalLocations, patrolCarCapacity);
        out.print(distance);
        out.flush();
    }

    protected static long calcDistance(int[] criminals, int patrolCapacity) {
        // put patrol on the position of the middle criminal
        int patrolPosition = criminals[criminals.length / 2];

        double itr = (criminals.length - 1) / 2.0;
        // number of travels to the left from the police station
        int itrLeft = (int) Math.ceil(Math.ceil(itr) / ((double) patrolCapacity));
        //number of travels to the right from the police station
        int itrRight = (int) Math.ceil(Math.floor(itr) / ((double) patrolCapacity));

        long distance = 0;

        int lo = 0;
        while (itrLeft-- > 0) {
            distance += patrolPosition - criminals[lo];
            lo = lo + patrolCapacity;
        }

        int hi = criminals.length - 1;
        while (itrRight-- > 0) {
            distance += criminals[hi] - patrolPosition;
            hi -= patrolCapacity;
        }
        return 2 * distance;
    }
}


更新:如果您对解决Codeforce问题不感兴趣,请定义最简单的任务。

Input:
arraySize
step
array

Output:
Number that represents summary of all Math.abs(array[array.length / 2] - array[i]) for all `i % step == 0`

最佳答案

Scanner is notoriously slow。我将accepted with your code替换为更快的实现。该代码取自IFMO training Java template

static class FastScanner {
    BufferedReader br;
    StringTokenizer st;

    FastScanner(InputStream f) {
        br = new BufferedReader(new InputStreamReader(f));
    }

    String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
}


对于输入中的1M整数,这将在我的机器上将输入解析所需的时间从〜1.3s减少到了〜0.35s,这提高了4倍。

09-10 06:38
查看更多