[leetcode/lintcode 题解] 阿里算法面试题：切割剩余金属

描述
金属棒工厂的厂长拥有 n 根多余的金属棒。当地的一个承包商提出，只要所有的棒材具有相同的长度（用 saleLength 表示棒材的长度），就将金属棒工厂的剩余棒材全部购买。厂长可以通过将每根棒材切割零次或多次来增加可销售的棒材数量，但是每次切割都会产生一定的成本（用 costPerCut 表示每次切割的成本）。等所有的切割完成以后，多余的棒材将被丢弃，没有利润。金属棒工厂的厂长获得的销售总利润计算公式如下：
totalProfit = totalUniformRods saleLength salePrice - totalCuts * costPerCut
其中 totalUniformRods 是可销售的金属棒数量，salePrice 是承包商同意支付的每单位长度价格，totalCuts是需要切割棒材的次数。

1≤n≤501≤n≤50
1≤lengths[i]≤1041≤lengths[i]≤10^4
1≤salePrice,costPerCut≤1031≤salePrice,costPerCut≤10^3

在线评测地址：领扣题库官网
https://www.lintcode.com/problem/1917/?utm_source=sc-tianchi-sz-0412

样例1
输入：
1
10
[30,59,110]
输出：
1913

算法 ：模拟、暴力
解题思路
因为金属数量比较少，可以使用暴力遍历来寻找最优切割长度，在计算时要注意切割次数，如果刚好能够切成整数份（没有剩余金属）的话，是可以少切一刀的。
复杂度分析
时间复杂度：O(L*n)
L是最长金属的长度，n为金属数量
空间复杂度：O(1)
不需要额外空间
源代码

public class Solution {
    /**
     * @param costPerCut: integer cost to make a cut 
     * @param salePrice: integer per unit length sales price 
     * @param lengths: an array of integer rod lengths 
     * @return: The function must return an integer that denotes the maximum possible profit. 
     */
    public int maxProfit(int costPerCut, int salePrice, int[] lengths) {
        int profit = 0;
        int maxLen = 0;
        for (int i = 0; i < lengths.length; i++) {
            maxLen = Math.max(maxLen, lengths[i]);
        }
        
        for (int length = 1; length <= maxLen; length++) {
            int cut = 0, pieces = 0;
            for (int i = 0; i < lengths.length; i++) {
                int curCut = (lengths[i] - 1) / length;
                int curPiece = lengths[i] / length;
                if (length * salePrice * curPiece - costPerCut * curCut > 0) {
                    cut += curCut;
                    pieces += curPiece;
                }
            }
            profit = Math.max(profit, length * salePrice * pieces - costPerCut * cut);
        }
        
        return profit;
    }
}

更多题解参考：九章官网solution