Как исправить случаи недоучета в этой проблеме Java HW (серебро USACO) - PullRequest
Новая
       39

Как исправить случаи недоучета в этой проблеме Java HW (серебро USACO)

0 голосов
/ 16 февраля 2019

Я наткнулся на проблему USACO, которую я не могу решить, и кажется, что в каждом случае, когда я ошибаюсь, моя программа всегда недооценивает количество решений.Описание проблемы здесь (http://www.usaco.org/index.php?page=viewproblem2&cpid=714),, но я могу предоставить его более короткую версию

В основном вам дают несколько кур и коров (n <= 20000), где у каждой курицы естьзначение int x_n, и у каждой коровы есть значения int a_n и b_n (они не должны различаться). Вы хотите найти максимальное количество пар курица-корова, где пара определяется как: a_n <= x_n <=b_n. Как только курица или корова в паре, они не могут соединиться с кем-либо еще </p>

Как я ошибся? 

    PriorityQueue<Integer> pqChicken = new PriorityQueue<Integer>();
    PriorityQueue<State> pqCow = new PriorityQueue<State>();

    //read in info for chicken and cow pq (not shown)

    int ret = 0; //to record number of pairs
    while (pqChicken.size() != 0 && pqCow.size() != 0) {

        int chicken = pqChicken.peek();
        State cow = pqCow.peek();
        if (chicken < cow.low) {      //all cows are above this chicken, it can't pair
            pqChicken.poll();

        } else if (chicken > cow.high) { //all chickens are above this cow, it can't pair
            pqCow.poll();

        } else {                    //it can pair, pair them and update the number of pairs
            ret++;
            pqChicken.poll();
            pqCow.poll();
        }
    }
    System.out.println(ret);

Вот класс коровы: 

static class State implements Comparable<State> {
    int low,high;  //low, high
    public State(int low,int high) {
        this.low=low;
        this.high=high;
    }
    public int compareTo(State a) { //sort by decreasing low, then decreasing high
        if (low > a.low)
            return 1;               //I think testing a case for equality won't matter
        if (low == a.low && high > a.high)
            return 1;

        return -1;
    }
}
...