Advertisement
Guest User

Untitled

a guest
Aug 20th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.74 KB | None | 0 0
  1. def minimumTotalPower(treasureBoxes, k):
  2.     n = len(treasureBoxes)
  3.     assert(1 <= n and n <= 200000)
  4.    
  5.     for i in range(n):
  6.         assert(treasureBoxes[i] == 0 or treasureBoxes[i] == 1)
  7.        
  8.     assert(1 <= k and k <= 100)
  9.    
  10.     cur = 0
  11.     pos = 0
  12.    
  13.     v = []
  14.     num = 0
  15.    
  16.     for i, x in enumerate(treasureBoxes):
  17.         if (x == 0):
  18.             continue
  19.         cur += i - pos
  20.         v.append(i - pos)
  21.         pos += 1
  22.         num += 1
  23.        
  24.     l = 0
  25.    
  26.     ans = cur
  27.    
  28.     v.sort()
  29.    
  30.     for i in range(1, n - num + 1):
  31.         while (l < len(v) and v[l] < i):
  32.             l += 1
  33.         cur += l
  34.         cur -= len(v) - l
  35.         ans = min(ans, cur)
  36.        
  37.     return ans * k
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement