Hackerrank_CubesAndCylinders [source code]

public class Hackerrank_CubesAndCylinders {
static
/******************************************************************************/
public class Solution {
    static boolean DEBUG = true;
    /*
     * Complete the function below.
     */
    static int maximumPackages(int[] S, int[] K, int[] R, int[] C) {
         // Return the maximum number of packages that can be put in the containers.]
        PriorityQueue<Pair> packages = new PriorityQueue<> ((a, b) -> a.size - b.size), containers = new PriorityQueue<> ((a, b) -> a.size - b.size);
        for (int i = 0; i < S.length; i++)
            packages.offer (new Pair (S[i], K[i]));
        for (int i = 0; i < R.length; i++)
            containers.offer (new Pair (R[i], C[i]));
        int res = 0;
        while (!containers.isEmpty ()) {
            Pair cur_container = containers.peek ();
            if (packages.isEmpty ())
                break;
            if (cur_container.size * 2 <= Math.sqrt (2) * packages.peek().size) {
                containers.poll ();
                continue;
            }
            Pair cur_package = packages.peek ();
            int push_count = Math.min (cur_container.count, cur_package.count);
            res += push_count;
            cur_container.count -= push_count;
            cur_package.count -= push_count;
            if (cur_container.count == 0)
                containers.poll ();
            if (cur_package.count == 0)
                packages.poll ();
        }
        return res;
    }

    static class Pair {
        int size, count;
        Pair (int s, int c) {this.size = s; this.count = c; }
        public String toString () {
            return String.format ("[%d has %d]", size, count);
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        Hackerrank_CubesAndCylinders.Solution tester = new Hackerrank_CubesAndCylinders.Solution();
        String[] inputs = {
            "1 2", "1 1", "1 2", "1 1", "2",
            "1 2", "3 3", "1 2", "3 3", "6",
            "1 2", "3 3", "1 2", "3 1", "4",
        };
        for (int i = 0; i < inputs.length / 5; i++) {
            int[] S = parseString (inputs[5 * i]), K = parseString (inputs[5 * i + 1]), R = parseString (inputs[5 * i + 2]), C = parseString (inputs[5 * i + 3]);
            int ans = Integer.parseInt (inputs[5 * i + 4]);
            System.out.println (Printer.separator ());
            int output = tester.maximumPackages (S, K, R, C);
            System.out.printf ("%s\n -> %s, expected: %d\n", 
                Arrays.deepToString (new int[][] {S, K, R, C}), Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }

    static int[] parseString (String line) {
        String[] tokens = line.trim ().split ("\\s+");
        int[] res = new int[tokens.length];
        for (int i = 0; i < tokens.length; i++)
            res[i] = Integer.parseInt (tokens[i]);
        return res;
    }
}

还是那句话, 自己定义一个class, 比用int array方便很多;

这个题目很有意思啊, 一开始的想法是从大头开始:

    static int maximumPackages(int[] S, int[] K, int[] R, int[] C) {  
         // Return the maximum number of packages that can be put in the containers.]  
        PriorityQueue<Pair> packages = new PriorityQueue<> ((a, b) -> b.size - a.size), containers = new PriorityQueue<> ((a, b) -> b.size - a.size);  
        for (int i = 0; i < S.length; i++)  
            packages.offer (new Pair (S[i], K[i]));  
        for (int i = 0; i < R.length; i++)  
            containers.offer (new Pair (R[i], C[i]));  
        int res = 0;  
        while (!containers.isEmpty ()) {  
            if (DEBUG) System.out.printf ("%s\n%s, res:(%d)\n", packages, containers, res);  
            Pair cur_container = containers.peek ();  
            while (packages.peek ().size * Math.sqrt (2) >= 2 * cur_container.size)  
                packages.poll ();  
            if (packages.isEmpty ())  
                break;  
            Pair cur_package = packages.peek ();  
            int push_count = Math.min (cur_package.count, cur_container.count);  
            if (DEBUG) System.out.println (push_count);  
            res += push_count;  
            cur_package.count -= push_count;  
            cur_container.count -= push_count;  
            if (cur_container.count == 0) {  
                containers.poll ();  
            }  
            if (cur_package.count == 0) {  
                packages.poll ();  
            }  
            if (DEBUG) System.out.println ();  
        }  
        return res;  
    }

但是这个代码错的厉害;

然后后来被大神提示, 反过来方向, 就过了很多. 不知道为什么;

另外, 这题是不需要用PriorityQueue的;

最后还是调出来了, 一个很花时间的bug是:

            if (packages.isEmpty ())  
                break;

这个一开始没有加, 然后死活过不了了; 后来自己过代码, 看到peek, 就立刻想到要检查合法性, 然后就想起来了; 只能说好习惯还是重要;

Problem Description

https://www.hackerrank.com/contests/university-codesprint-4/challenges/cubes-and-cylinders/problem