Время доения USACO Training (наибольшее время без доения) - 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

Ваше решение кажется неправильным.

Основная ошибка - это предположение, которое вы явно сделали, что вы можете найти все важные корреляции между заданными интервалами за один проход по таблице. Увы, постановка задачи делает без гарантии интервалы указаны в произвольном c порядке. В нем даже специально упоминается, что есть несколько «фермеров» доения, поэтому их соответствующие графики могут сделать общий ввод неупорядоченным при объединении, даже если каждое расписание упорядочено. Это случай данных вашего примера, которые содержат упорядоченный запуск из десяти интервалов

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

, а затем еще один бег с одним интервалом

[1. 20]

, который охватывает первое.

Чтобы справиться с этим, я бы рекомендовал отсортировать данные по времени начала интервалов:

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

Каждые два интервала с одинаковым временем начала перекрываются, и теперь они находятся в непрерывном блоке массив, поэтому мы можем легко их найти. Кроме того, 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 -й, если 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;
    }