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 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告