描述

鬼谷子非常聰明，正因?yàn)檫@樣，他非常繁忙，經(jīng)常有各諸侯車的特派員前來(lái)向他咨詢時(shí)政。有一天，他在咸陽(yáng)游歷的時(shí)候，朋友告訴他在咸陽(yáng)最大的拍賣行（聚寶商行）將要舉行一場(chǎng)拍賣會(huì)，其中有一件寶物引起了他極大的興趣，那就是無(wú)字天書。但是，他的行程安排得很滿，他他已經(jīng)買好了去邯鄲的長(zhǎng)途馬車標(biāo)，不巧的是出發(fā)時(shí)間是在拍賣會(huì)快要結(jié)束的時(shí)候。于是，他決定事先做好準(zhǔn)備，將自己的金幣數(shù)好并用一個(gè)個(gè)的小錢袋裝好，以便在他現(xiàn)有金幣的支付能力下，任何數(shù)目的金幣他都能用這些封閉好的小錢的組合來(lái)付賬。鬼谷子也是一個(gè)非常節(jié)儉的人，他想方設(shè)法使自己在滿足上述要求的前提下，所用的錢袋數(shù)最少，并且不有兩個(gè)錢袋裝有相同的大于1的金幣數(shù)。假設(shè)他有m個(gè)金幣，你能猜到他會(huì)用多少個(gè)錢袋，并且每個(gè)錢袋裝多少個(gè)金幣嗎？

---

分析

• 可能有點(diǎn)水, 但這種題做的很少, 還是練習(xí)一下比較好
• 考慮二進(jìn)制
• 任何數(shù)都可用2的冪次方加和得到.
• 那么把m個(gè)金幣拆成幾個(gè)2的冪次方的數(shù)就可以湊出任何 1~m 之間的數(shù)了. 但是不一定會(huì)正好, 把剩下的錢拆成單獨(dú)一份, 答案就是第一個(gè)大于m的2^n的那個(gè)n. 那如果正好拆完呢? 因?yàn)樽詈笠环莶豢梢允莔, 所以還是要把m拆開(kāi), 結(jié)果還是一樣.
• 為什么是二進(jìn)制不是其他進(jìn)制呢? 因?yàn)槿魏螖?shù)都可用2的冪次方加和得到. 但其他的就不一定了.

---

代碼

https://code.csdn.net/snippets/612326

總結(jié)

以上是生活随笔為你收集整理的BZOJ-1192-鬼谷子的钱袋的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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