資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：在遵守規則的情況下分發糖果，計算有多少孩子能拿到糖果
假設我們有k個糖果。我們必須把它們分發給孩子們。現在有一些規則：
- 第i個孩子將得到i²個糖果
- 在第i個孩子之前，索引從1到i-1的所有孩子都必須先得到糖果。
- 如果第i個孩子沒有得到i²個糖果，則該分配無效。
因此，如果輸入是k = 20，則輸出將是3，因為第一個孩子將得到1，第二個孩子將得到2² = 4，第三個孩子將得到3² = 9，但第四個孩子需要4² = 16，而我們只有6個糖果剩餘，所以這是一個無效的分配，因此只有三個孩子將得到糖果。
為了解決這個問題，我們將遵循以下步驟：
- left := 0, right := k
- 當 right - left > 1 時，執行：
- mid := floor((left + right) / 2)
- 如果 floor(mid * (mid + 1) * (2 * mid + 1) / 6) > k，則
- right := mid
- 否則，
- left := mid
- 如果 right * (right + 1) * (2 * right + 1) <= k * 6，則
- 返回 right
- 返回 left
示例
讓我們看看下面的實現，以便更好地理解：
def solve(k):
left = 0
right = k
while (right - left > 1):
mid = (left + right) // 2
if (mid * (mid + 1) * (2 * mid + 1) // 6 > k):
right = mid
else:
left = mid
if (right * (right + 1) * (2 * right + 1) <= k * 6):
return right
return left
k = 20
print(solve(k))輸入
20
輸出
3
更新於：2021年10月25日
267 次瀏覽
廣告