ログを切り捨ててPythonのデータベースに完全に保存するための最大サイズを見つけるプログラム

ログと呼ばれる数値のリストと別の値の制限があるとします。 logs [i]の各要素は、i番目のユーザーによって生成されたログのサイズを表します。また、limitは、データベースに保存できるログの合計サイズを表します。ログ内のすべてのログを切り捨てて最大サイズxになり、左側のログサイズの合計が最大で制限されるように、最大​​のxを見つける必要があります。ログを切り捨てる必要がない場合は、最大のログサイズを返すだけです。

したがって、入力がlogs =[500、200、10000、500、4000] limit =3000のようである場合、ログを900に切り捨てるため、出力は900になり、[500、200、900、500 、900]現在の合計は3000

これを解決するには、次の手順に従います-

• lo：=0
• hi：=1+ログの最大数
• lo + 1 <こんにちは、do
  • mi：=lo +（hi --lo）/2のフロア
  • リストに存在するすべての要素の合計が（ログの各ログインのmiとlogの最小値）<=limitの場合、
    • lo：=mi
  • それ以外の場合、
    • こんにちは：=mi
• return 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