Source: Magician and Chocolates

Problem Description

Given N bags, each bag contains Bi chocolates. There is a kid and a magician. In one unit of time, kid chooses a random bag i, eats Bi chocolates, then the magician fills the ith bag with floor(Bi/2) chocolates.

Find the maximum number of chocolates that kid can eat in A units of time.

NOTE:

  1. floor() function returns the largest integer less than or equal to a given number.
  2. Return your answer modulo 109+7

Input Format

First argument is an integer A.
Second argument is an integer array B of size N.

Output Format

Return an integer denoting the maximum number of chocolates that kid can eat in A units of time.

Example Input

Input 1:

 A = 3
 B = [6, 5]

Input 2:

 A = 5
 b = [2, 4, 6, 8, 10]

Example Output

Output 1:

 14

Output 2:

 33

Example Explanation

Explanation 1:

 At t = 1 kid eats 6 chocolates from bag 0, and the bag gets filled by 3 chocolates. 
 At t = 2 kid eats 5 chocolates from bag 1, and the bag gets filled by 2 chocolates. 
 At t = 3 kid eats 3 chocolates from bag 0, and the bag gets filled by 1 chocolate. 
 so, total number of chocolates eaten are 6 + 5 + 3 = 14

解題：

這題原理跟 InterviewBit – N max pair combinations 基本上一模一樣，但筆者極度不解的地方是：原始碼一模一樣，將其複製貼上到網站的 IDE 上執行會不斷出現 TLE ；但用 import heapq 的方式卻可以在不觸發 TLE 的情況下解題。覺得頭很痛。

另外還有一個神秘的地方是 heapq 模組內有針對 Max_heap 的 _heappop_max 程式，但對加入資料的 heappush 卻沒有相對應於 Max_heap 結構的 _heappush_max ，這樣在執行 heappush 的時候還不是會遇到一堆有的沒的錯誤要 debug…… 到底為何啊。

Code:

import heapq
class Solution:
    # @param T : integer, how many times the kid eat chocolates
    # @param chocs : list of integers
    # @return an integer
    def nchoc(self, T, chocs):
        total_choc = 0
        for i in range(len(chocs)):
            chocs[i] = chocs[i] * -1
        chocs = sorted(chocs)
        for _ in range(T):
            if not chocs: break
            choc = heapq.heappop(chocs)
            total_choc = (total_choc - choc) % (10**9 + 7)
            #put chocs back
            if (-choc)//2 < 1: continue
            heapq.heappush(chocs, -((-choc)//2))
        return total_choc

GitHub: GitHub

發表留言