0

我偶然发现了一个我似乎无法解决的 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。一旦鸡或牛配对，它们就不能与其他任何人配对

我怎么错了？

    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;
    }
}
4

0 回答 0