当前位置: 首页 > news >正文

[题解] 分竹子

传送门

题目描述

bamboo_len 的竹子砍为若干整数段, 求每段竹子长度的最大乘积. 2 <= bamboo_len <= 58

分析

设将长度为 \(s\) 的竹子分为 \(n\) 段, 每段分别为 \(a_1, a_2, \cdots, a_n\) , 问题转化为求 \(\max a_1a_2\cdots a_n\)

由均值不等式: \((a_1a_2\cdots a_n)^{1/n} \leqslant \frac{a_1 + a_2 +\cdots + a_n}{n}\) , 当且仅当 \(a_1 = a_2 = \cdots a_n\) 时取等, 此时 \(a_1a_2\cdots a_n = (\frac{a_1+a_2+\cdots+a_n}{n})^n = (\frac{s}{n})^n\) .

取对数得 \(n \ln \frac{s}{n} = n \ln s - n \ln n\) , 求导得 \(\ln s - 1 - \ln n\) , 则当 \(\frac{s}{n} = e\) 时导数为 \(0\) , 取得最大值. 此时 \(n = \frac{s}{e}\) , 每段长 \(\frac{s}{n} = e\) , 所以尽量分为长度为 \(3\) 的段.

代码

class Solution:def cuttingBamboo(self, bamboo_len: int) -> int: if bamboo_len <= 3:return bamboo_len - 1left = bamboo_len % 3k = bamboo_len // 3if left == 0:return 3 ** kelif left == 1:return 3 ** (k - 1) * 4else:return 3 ** k * 2   
http://www.hskmm.com/?act=detail&tid=25231

相关文章:

  • 分数规划
  • CSS - transition 粗浅记忆
  • 【MC】LittleTiles模组结构数据解析和版本迁移方案
  • 容器魔方导致盒子满了
  • 课程学习笔记——[大一秋]遗传学
  • P3067 [USACO12OPEN] Balanced Cow Subsets G
  • Vivado 2025 界面中文设置
  • 词汇学习——专业词汇
  • P4556 [Vani有约会] 雨天的尾巴 [模板] 线段树合并
  • P4550 收集邮票
  • P8110 [Cnoi2021] 矩阵
  • P9751 [CSP-J 2023] 旅游巴士
  • P9234 [蓝桥杯 2023 省 A] 买瓜
  • P1044 [NOIP 2003 普及组] 栈
  • P1080 [NOIP 2012 提高组] 国王游戏
  • 音响没声音
  • P1654 OSU!
  • DynamoDB十年演进:云原生数据库的技术革新
  • 完整教程:MySQL全量、增量备份与恢复
  • 10/5
  • 10/4
  • 嵌入式MCU
  • porting perf性能观测工具
  • Windows常用快捷指令
  • Python 在金融中的应用- Part 1 - 教程
  • QBXT2025S刷题 Day4
  • java学习日记9.25
  • porting 开源memtester
  • 计算机的组成
  • 完整教程:用mediamtx搭建简易rtmp,rtsp视频服务器