首頁>Club>
10
回覆列表
  • 1 # 使用者2686893526612

    @管清文 的答案早了一步TAT12個是可以的,方案是1,1,1,2,2,3,4,5,7,9,12,16我是這樣想的,首先加強條件,要求“三個人都打相同數目的飯n”,再考慮只需要滿足“已有盤子中的飯的總重量超過需要供應的飯的總重量”,這時所需要盤子的數目的下界顯然也是原問題的一個下界。n=1時,顯然需要1,1,1這3個盤子;n=2時,共需要分量為2*3=6的飯,而已有盤子中的分量為3,至少再要2個分量<=2的盤子;n=3時,共需要分量為3*3=9的飯,而已有盤子中的分量至多為7,至少再要1個分量<=3的盤子;n=4時,共需要分量為3*4=12的飯,而已有盤子中的分量至多為10,至少再要1個分量<=4的盤子;n=5時,共需要分量為3*5=15的飯,而已有盤子中的分量至多為14,至少再要1個分量<=5的盤子;n=6時,共需要分量為3*6=18的飯,而已有盤子中的分量至多為19,此時不需要額外的盤子;n=7時,共需要分量為3*7=21的飯,而已有盤子中的分量至多為19,至少再要1個分量<=7的盤子;n=8時,共需要分量為3*8=24的飯,而已有盤子中的分量至多為26,此時不需要額外的盤子;n=9時,共需要分量為3*9=27的飯,而已有盤子中的分量至多為26,至少再要1個分量<=9的盤子;依此類推,在n=12、16時各再需要一個分量<=12和<=16的盤子。因此,12個盤子是盤子數目的下界,至少需要12個盤子才能滿足“都打相同數目的飯”的情況下對"總重量"的要求(但可能不滿足原問題的要求)。注意到上述過程中給出了一個12個盤子的組合,就是(1,1,1,2,2,3,4,5,7,9,12,16),經程式驗證(╮(╯_╰)╭),這個組合可以解決原問題(只需要使用貪心的做法,不斷地把當前最大的盤子提供給當前最需要飯的那個人),因此原問題的答案就是12個盤子。附醜陋的程式碼:

  • 2 # lanfengz1

    從菜碗考慮,人數必須是2的倍數,否則會有“破碗”(也就是非整數)。

    同理,從湯碗考慮,人數必須是3的倍數。

    所以,實際人數必須是6的倍數。

    6人:6飯碗+3菜碗+2湯碗=11碗。

    這是“試湊法”,碗數較少時很容易計算。

    如果數字很大,比如110個碗,最好用解方程了。參見deer1515老師的方程式。

  • 中秋節和大豐收的關聯?
  • 英雄聯盟中加速最多的鞋子?