美国编码奥林匹克第一次超时和/或太多记忆

Question

几天前，我第一次参加了美国编码奥林匹克运动会，并且在我的所有代码上都出现了同样的错误。我无法弄清楚为什么因为它告诉我在第一个测试用例上做得非常好，所以我不明白其他9个如何超时。有人可以解释我的代码有什么问题。 Problem Error Message

import java.io.*;
public class milkmeasure {
    private static int [] cows ={7,7,7};
    public static void main(String[] args) throws IOException {
        // initialize file I/O
        BufferedReader br = new BufferedReader(new FileReader("measurement.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("measurement.out")));
        int N = Integer.parseInt(br.readLine());
        String [] entries = new String [N];
        for (int i=0;i<N;i++){
            entries [i]= br.readLine();
        }
        int topCow = 1;
        int finalN = 0;
        for (int i=0; i<N; i++){
            String lowEntry = entries[lownum(N,entries)];
            String name = lowEntry.substring(2,lowEntry.substring(2).indexOf(" ")+2);
            int effect = Integer.parseInt(lowEntry.substring(lowEntry.substring(2).indexOf(" ")+3));
            if (name.equals("Bessie")){cows[1]+=effect;}
            else if (name.equals("Elsie")){cows[2]+=effect;}
            else if (name.equals("Mildred")){cows[0]+=effect;}
            int newTop = findTop();
            if (newTop!=topCow){finalN++;}
            topCow = newTop;
            entries[lownum(N,entries)]="101 ";
        }
        pw.println(finalN);
        pw.close();
    }

    private static int lownum (int N, String [] entries){
        int lowNum = 101;
        int returnInt=0;
        for (int i =0; i<N; i++){
            int a = Integer.parseInt(entries[i].substring(0,entries[i].indexOf(" ")));
            if (a<lowNum){
                lowNum = a;
                returnInt =i;
            }
        }
        return returnInt;
    }

    private static int findTop (){
        int maxval = 0;
        int returnval =0;
        for (int i =0; i<3; i++){
            if (cows[i]>= maxval){
                returnval += cows[i]*cows[i];
                maxval=cows[i];
            }
        }
        return returnval;
    }
}

Answer 1

算法复杂性问题

对于每个条目，您的main()方法调用lownum()（两次）。 lownum()扫描所有条目以识别并返回具有最低日期编号的条目。总的来说，程序的复杂性至少会在条目数量上缩放为o（N2）。

通过对条目进行一次排序然后简单地按顺序处理它们，可以将该下限减少到o（N log N）。

通过对条目的最大日期数的合理限制，以及每天最多有一个条目的给定保证，可以通过将条目分配到与其对应的位置的数组或列表来进一步减少到o（N）。日期数字，因此不需要实际排序。

事实证明，这是渐近复杂度的主要驱动因素，因此改善此下限也可以改善上限，一直到O（N）。

一般效率问题

由于问题规定每天最多只有一次条目持续100天，因此您可能处于一个仍然受影响成本系数的（效率）影响很大的制度。事实上，你有很多低效率。其中：

• 您可以多次解析每个条目，扫描以将它们拆分为字段并将其中一些转换为整数。这非常浪费。解析每个条目一次，然后存储解析的结果会更有效。实际上，您可以使用Scanner在输入处获得几乎免费的解析。
• 您为每个条目调用两次lownum()方法。如上所述，该方法的当前实现是昂贵的，并且在第一次和第二次调用之间没有任何变化会影响结果。
• （次要）你对牛的名字进行完整的字符串比较，即使只看他们的第一个字母就足够了
• （次要）你调用单独的方法来查找下一个条目并计算新的顶级牛。方法调用比较昂贵，因此对大量的方法调用进行很少的工作是有点低效的。但是，这可能不会对您的特定代码产生重大影响。