find-minimum-log-transportation-cost

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given integers <code>n</code>, <code>m</code>, and <code>k</code>.

There are two logs of lengths <code>n</code> and <code>m</code> units, which need to be transported in three trucks where each truck can carry one log with length at most <code>k</code> units.

You may cut the logs into smaller pieces, where the cost of cutting a log of length <code>x</code> into logs of length <code>len1</code> and <code>len2</code> is <code>cost = len1 * len2</code> such that <code>len1 + len2 = x</code>.

Return the minimum total cost to distribute the logs onto the trucks. If the logs don&#39;t need to be cut, the total cost is 0.

&nbsp;
Example 1:

<div class="example-block">
Input: n = 6, m = 5, k = 5

Output: 5

Explanation:

Cut the log with length 6 into logs with length 1 and 5, at a cost equal to <code>1 * 5 == 5</code>. Now the three logs of length 1, 5, and 5 can fit in one truck each.
</div>

Example 2:

<div class="example-block">
Input: n = 4, m = 4, k = 6

Output: 0

Explanation:

The two logs can fit in the trucks already, hence we don&#39;t need to cut the logs.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= k &lt;= 105</code></li>
	<li><code>1 &lt;= n, m &lt;= 2 * k</code></li>
	<li>The input is generated such that it is always possible to transport the logs.</li>
</ul>

第 451 场周赛

weekly-contest-451

minCuttingCost

中级工程师

Find Minimum Log Transportation Cost

Math

给你三个整数 <code>n</code>、<code>m</code> 和 <code>k</code>。

有两根长度分别为 <code>n</code> 和 <code>m</code> 单位的木材，需要通过三辆卡车运输。每辆卡车最多只能装载一根长度&nbsp;不超过 <code>k</code> 单位的木材。

你可以将木材切成更小的段，其中将长度为 <code>x</code> 的木材切割成长度为 <code>len1</code> 和 <code>len2</code> 的段的成本为 <code>cost = len1 * len2</code>，并且满足 <code>len1 + len2 = x</code>。

返回将木材分配到卡车上的&nbsp;最小总成本&nbsp;。如果木材不需要切割，总成本为 0。

&nbsp;

示例 1：

<div class="example-block">
输入： n = 6, m = 5, k = 5

输出： 5

解释：

将长度为 6 的木材切割成长度为 1 和 5 的两段，成本为 <code>1 * 5 == 5</code>。现在三段长度分别为 1、5 和 5 的木材可以分别装载到每辆卡车。
</div>

示例 2：

<div class="example-block">
输入： n = 4, m = 4, k = 6

输出： 0

解释：

两根木材已经可以直接装载到卡车上，因此不需要切割。
</div>

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= k &lt;= 105</code></li>
	<li><code>1 &lt;= n, m &lt;= 2 * k</code></li>
	<li>输入数据保证木材总存在能被运输的方案。</li>
</ul>