Python程序：查找最大截断日志大小以将其完全存储在数据库中

假设我们有一个名为logs的数字列表和另一个值limit。logs[i]中的每个元素代表第i个用户生成的日志大小。limit代表我们可以在数据库中存储的日志总大小。我们必须找到最大的x，这样如果我们将logs中的每个日志截断到最多x大小，并且剩余日志大小的总和最多为limit。如果不需要截断任何日志，则直接返回最大的日志大小。

因此，如果输入类似于logs = [500, 200, 10000, 500, 4000] limit = 3000，则输出将为900，因为我们将日志截断到900，然后我们可以得到[500, 200, 900, 500, 900]，现在的总和是3000。

为了解决这个问题，我们将遵循以下步骤：

  • lo := 0
  • hi := logs最大值 + 1
  • 当 lo + 1 < hi 时，执行：
    • mi := lo + floor((hi - lo)/2)
    • 如果logs列表中所有元素（每个日志取mi和日志本身的最小值）的总和 <= limit，则：
      • lo := mi
    • 否则：
      • hi := mi
  • 返回 lo

示例

让我们看下面的实现来更好地理解：

def solve(logs, limit):
   lo, hi = 0, max(logs) + 1
   while lo + 1 < hi:
      mi = lo + (hi - lo) // 2
      if sum(min(mi, log) for log in logs) <= limit:
         lo = mi
      else:
         hi = mi
   return lo

logs = [500, 200, 10000, 500, 4000]
limit = 3000
print(solve(logs, limit))

输入

[500, 200, 10000, 500, 4000], 3000

输出

900

更新于：2021年10月19日

97 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告