LintCode 1917. 切割剩余金属

totalProfit = totalUniformRods * saleLength * salePrice - totalCuts * costPerCut

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

class Solution {
public:
    /**
     * @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. 
     */
    int maxProfit(int costPerCut, int salePrice, vector<int> &lengths) {
        // write your code here
        int maxprofit = 0, profit = 0;
        for(int L = 1; L <= 10000; ++L)
        {
            profit = 0;
            for(auto l : lengths)
            {
                int n = l/L;
                int cut = 0;
                if(l%L == 0)
                    cut = n-1;
                else
                    cut = n;
                profit += n*salePrice*L - cut*costPerCut;
            }
            maxprofit = max(maxprofit, profit);
        }
        return maxprofit;
    }
};