牛客網 2018校招真題 搜狐 包裹運輸

Description

牛客網 2018校招真題 包裹運輸

Solving Ideas

• 對于 6 × 6 的産品，每一個都需要一個包裹，而且無法填充
• 對于 5 × 5 的産品， 每一個都需要一個包裹，且包裹餘下空間隻能填充 1 × 1 的産品
• 對于 4 × 4 的産品， 每一個都需要一個包裹，餘下空間能填充 2 × 2 或 1 × 1 的産品，根據貪心的思想，優先并盡可能地填充 size 更大的産品
• 對于3 × 3 的産品，一個包裹最多能填充 4 個 3 × 3 的産品，如果 3 × 3 的産品不能填充滿一個包裹，則餘下空間能填充 2 × 2 或 1 × 1 的産品，同樣優先填充 size 更大的産品
• 對于 2 × 2 的産品，一個包裹最多能填充 9 個 2 × 2 的産品，如果 2 × 2 的産品不能填充滿一個包裹，則餘下空間能填充 1 × 1 的産品
• 最後計算需要多少個包裹來填充 1 × 1 的産品

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = br.readLine()) != null) {
            String[] strs = line.split(" ");
            int[] counts = new int[strs.length];
            boolean flag = true;
            for (int i = 0; i < strs.length; i++) {
                counts[i] = Integer.parseInt(strs[i]);
                if (flag && counts[i] != 0) flag = false;
            }
            if (flag) return;

            // 6 * 6
            int res = counts[5];

            // 5 * 5
            res += counts[4];
            counts[0] -= counts[4] * 11; //餘下空間用來填充 1 × 1 的産品

            // 4 * 4
            res += counts[3];
            int fillTwo = counts[3] * 5;
            // 先盡可能地用 2 × 2 的進行填充
            counts[1] -= (fillTwo >= counts[1]) ? counts[1] : fillTwo;
            // 然後用 1 × 1 的進行填充
            counts[0] -= (fillTwo >= counts[1]) ? (fillTwo - counts[1]) : 0;

            // 3 * 3
            int rmd = counts[2] % 4;
            res += (counts[2] / 4 + (rmd == 0 ? 0 : 1));
            int[] two = {0, 5, 3, 1}, one = {0, 27, 18, 9};
            if (rmd > 0) {
            	// 先盡可能地用 2 × 2 的進行填充
                counts[1] -= (two[rmd] >= counts[1]) ? counts[1] : two[rmd];
                // 然後用 1 × 1 的進行填充
                counts[0] -= (two[rmd] >= counts[1]) ? (one[rmd] - counts[1] * 4) : (8 - rmd);
            }

            // 2 * 2
            res += (counts[1] / 9  + (counts[1] % 9 == 0 ? 0 : 1));
            if (counts[1] % 9 > 0) counts[0] -= (36 - counts[1] % 9 * 4);

            // 1 * 1
            if (counts[1] > 0) res += (counts[0] / 36 + (counts[0] % 36 == 0 ? 0 : 1));
            System.out.println(res);
        }
    }
}