Re: [閒聊] 每日leetcode已回收
※ 引述《sustainer123 (caster )》之銘言：
: ※ 引述《oin1104 (是oin的說)》之銘言：
: : 題目翻譯：
: : 有一堆書 給你他們的寬跟高
: : 跟一個寬shelfWidth的書架
: : 每次放書都要照順序垂直放進去
: : 不可以疊在一起
: : 放滿了就放個隔板 然後去下一層放
: : 請問最少要多少高度的書架才能裝下所有書
: : 思路：
: : 我原本沒看到要找順序
: : 所以就sort然後從大賽到小
: : 幹咧
如果沒要求順序的話是 NP-complete
給定一個陣列 A[1..n]
把 shelfWidth 設為 sum(A[1..n])/2
且 n 本書的高度都設 1、寬度是 A[i]
則答案是 2 若且唯若存在 subset 的和恰等於 shelfWidth
所以可以 reduce 成 partition problem
不過 constraint 裡 shelfWidth 最大只有 1000 就是了
:)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722442704.A.C49.html
推
08/01 03:02,
1年前
, 1F
08/01 03:02, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 605 之 1548 篇)：