java - USACO 训练挤奶时间(最长非挤奶时间) - java

Question

我遇到了 Usaco 训练门的挤奶时间问题(又名 milk2)。我的代码适用于前几个问题，但随后不适用于其中一种情况。

问题在这里:http://jeremiahflaga.blogspot.com/2011/09/milking-cows-programming-problem-from.html

不起作用的情况是: [1, 2] [3, 4] [5, 6] [7, 8] [9, 10] [11, 12] [13, 14] [15, 16] [17, 18] [19, 20] [1, 20]

我认为这是因为最后一个 [1, 20]，它使我的代码无法工作，因为我认为我没有正确管理合并，但我已经尝试了一段时间并最终做出了代码更糟糕。

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

public class milk2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("milk2in.txt"));
        PrintWriter pw = new PrintWriter(new File("milk2.out"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        String line = "";
        int milkInterval = 0;
        int largestMilkInterval = 0;
        int noMilkInterval = 0;
        int largestNoMilkInterval = 0;
        milkingTime[] times = new milkingTime[N];
        for (int i = 0; i < times.length; i++) {
            st = new StringTokenizer(br.readLine());
            milkingTime mt = new milkingTime(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            times[i] = mt;
        }
        System.out.println(Arrays.toString(times));
        for (int i = 0; i < times.length - 1; i++) {
            noMilkInterval = 0;
            if (times[i].getEnd() >= times[i + 1].getStart()) {
                if (times[i].getStart() > times[i + 1].getStart()) {
                    milkInterval += times[i + 1].getEnd() - times[i + 1].getStart();
                } else {
                    milkInterval += (times[i].getEnd() - times[i].getStart()) + (times[i + 1].getEnd() - times[i + 1].getStart());
                }
                System.out.println("Milk Interval: " + milkInterval);
            } else {
                milkInterval += (times[i].getEnd() - times[i].getStart());
                if (milkInterval > largestMilkInterval) {
                    largestMilkInterval = milkInterval;
                }
                milkInterval = 0;
                noMilkInterval += times[i + 1].getStart() - times[i].getEnd();
                System.out.println("No milk interval: " + noMilkInterval);
            }
            if (noMilkInterval > largestNoMilkInterval) {
                largestNoMilkInterval = noMilkInterval;
            }
            if (milkInterval > largestMilkInterval) {
                largestMilkInterval = milkInterval;
            }

        }
        if (times.length == 1) {
            largestMilkInterval = times[0].getEnd() - times[0].getStart();
            largestNoMilkInterval = 0;
        }
        System.out.println("Largest Milk Interval: " + largestMilkInterval);
        System.out.println("Largest no milk Interval: " + largestNoMilkInterval);
        // pw.println(largestMilkInterval + " " + largestNoMilkInterval);
        // pw.close();
    }

}

class milkingTime {
    private int start;
    private int end;

    public milkingTime(int s, int e) {
        start = s;
        end = e;
    }

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    public String toString() {
        return "Start: " + start + " End: " + end;
    }
}

我也想知道我的代码是否完全错误，这不是解决这个问题的正确方向。

Answer 1

您的解决方案似乎是错误的。

主要错误是您显然做出的一个假设，您可以在一次遍历表格中找到给定间隔之间的所有重要相关性。遗憾的是，问题表述不能保证间隔按任何特定顺序给出。它甚至特别提到有几个“农民”在挤奶——因此，即使每个计划都是有序的，他们各自的计划在连接时可能会导致总输入无序。这是示例数据中的一种情况，其中包含十个间隔的有序运行

[1, 2] [3, 4] ... [19, 20]

然后再进行一次单间隔运行

[1. 20]

其中涵盖了前者。

为了解决这个问题，我建议按间隔的开始时间对数据进行排序:

[1, 2] [1, 20] [3, 4] ... [19, 20]

每两个具有相同开始时间的间隔重叠，现在它们位于数组的连续 block 中，因此我们可以轻松找到它们。此外，当且仅当第 i 个间隔与第 k 个间隔同时结束或晚于第 i 个间隔开始时，第 k 个间隔与其他一些间隔重叠(其中 i 小于 k )。

这就是我合并它们的方式:

    int curr = 0;    // the interval to receive a merge
    int next = 1;    // the interval to be possibly merged into current

    while (next < N)
    {
        if (times[curr].getEnd() >= times[next].getStart()) // overlapping?
        {
            times[curr].expandTo( times[next].getEnd() );   // merge to the current
        }
        else
        {
            ++ curr;                          // finished merging to current
            if (curr != next)                 // some items got merged
                times[curr] = times[next];    // shift further items to emptied space
        }
        ++ next;
    }
    newN = curr + 1;        // number of separate intervals after all merges

由于之前的排序，我们知道第 k 个间隔不能在第 i 个 if i<k 之前开始，因此单个条件可靠地指示所有重叠。

当然，expandTo类中的milkingTime方法必须增加结束时间以覆盖给定值:

class milkingTime {

    .....

    public void expandTo(int targetTime)
    {
        if (getEnd() < targetTime) {
            setEnd(targetTime);
        }
    }
}

现在找到最长间隔和最长间隙就很简单了:

    int longestInterval = 0;
    for (int i = 0; i < newN; ++ i) {
        if (times[i].getLength() > longestInterval)
            longestInterval = times[i].getLength();
    }

    int longestGap = 0;
    for (int i = 1; i < newN; ++ i) {
        int gap = times[i].getStart() - times[i - 1].getEnd();
        if (gap > longestGap)
            longestGap = gap;
    }