文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

描述

金屬棒工廠的廠長(zhǎng)擁有 n 根多余的金屬棒。
當(dāng)?shù)氐囊粋€(gè)承包商提出，只要所有的棒材具有相同的長(zhǎng)度（用 saleLength 表示棒材的長(zhǎng)度），就將金屬棒工廠的剩余棒材全部購(gòu)買(mǎi)。
廠長(zhǎng)可以通過(guò)將每根棒材切割零次或多次來(lái)增加可銷(xiāo)售的棒材數(shù)量，但是每次切割都會(huì)產(chǎn)生一定的成本（用 costPerCut 表示每次切割的成本）。
等所有的切割完成以后，多余的棒材將被丟棄，沒(méi)有利潤(rùn)。

金屬棒工廠的廠長(zhǎng)獲得的銷(xiāo)售總利潤(rùn)計(jì)算公式如下：

totalProfit = totalUniformRods * saleLength * salePrice - totalCuts * costPerCut

其中 totalUniformRods 是可銷(xiāo)售的金屬棒數(shù)量，
salePrice 是承包商同意支付的每單位長(zhǎng)度價(jià)格，
totalCuts是需要切割棒材的次數(shù)。

樣例 1 輸入： 1 10 [30,59,110] 輸出： 1913

https://www.lintcode.com/problem/cutting-metal-surplus/description

2. 解題

• 暴力法

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 hereint 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;elsecut = n;profit += n*salePrice*L - cut*costPerCut;}maxprofit = max(maxprofit, profit);}return maxprofit;} };

101ms C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LintCode 1917. 切割剩余金属的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。