“This is the fourth day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Sponsored by Amazon company Leetcode Weekly Contest 276, looked at the list of the first is a player in Peking University, win glory for the country, as long as the first nationality is Chinese is good, our generation model, my level is ashamed, only make two, the third way overtime. The code is very simple, but the code is long and smelly, and it is not too Hard to understand.

describe

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the ith battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.

Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return the maximum number of minutes you can run all the n computers simultaneously.

Example 1:

Input: n = 2, batteries = [3,3] Output: 4 Explanation: Initially, insert battery 0 into the first computer and battery 1 into the second computer. After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute. At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead. By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running. We can run the two computers simultaneously for at most 4 minutes, so we return 4.Copy the code

Example 2:

Input: n = 2, batteries = [1,1,1,1]
Output: 2
Explanation: 
Initially, insert battery 0 into the first computer and battery 2 into the second computer. 
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. 
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.
Copy the code

Note:

1 <= n <= batteries.length <= 10^5
1 <= batteries[i] <= 10^9
Copy the code

parsing

Now there are n computers, given an integer n and an integer array with an index of 0 batteries, where the i-th battery will run the computer batteries[I] for minutes. We’re going to use a given battery to keep all n computers running at the same time. You can start with up to one battery per computer. Then, at any round number, we can pull the battery out of the computer and plug in another battery. The plugged battery can be a brand new battery, or it can be another computer’s used battery that still has power. Assuming that the unplug and plug process doesn’t take time, and the computer doesn’t shut down when the battery is pulled out. And the battery can’t be recharged the whole time, it just keeps draining. Returns the maximum number of minutes that all N machines can run simultaneously.

Actually, in hindsight, it’s not that hard. I have a picture here

The simplest way to think about it is to sort batteries in descending order, and then distribute the batteries in the batteries subarray to the first n computers, like pouring a glass of water into a pond of the first n batteries, so that the first n computers will have the highest minimum working time. The problem with O(n^2) is that I used the for loop twice, which caused me to run out of time because I was limited to batteries. Length is 10^5.

answer

class Solution(object):
	    def maxRunTime(self, n, batteries):
	        """
	        :type n: int
	        :type batteries: List[int]
	        :rtype: int
	        """
	        if n>len(batteries): return 0
	        batteries.sort(reverse=True)
	        b = batteries[:n]
	        t = batteries[n:]
	        for i in range(len(t)-1, -1, -1):
	            for _ in range(t[i]):
	                idx = b.index(min(b))
	                b[idx] += 1
	        return min(b)
		
Copy the code

The results

Time Limit Exceeded
Copy the code

parsing

This kind of Hard problem is like this. It seems easy to do, but it is difficult to do. It completely tests the comprehension level of the problem. The simplest idea is to divide all the batteries between n computers and find the minimum time to work, sum(batteries) // n minutes. But in this case, n = 2, batteries = [3,3,9], 7 is the wrong answer. That’s because the extra power from the third battery can only power one computer, not two. So we compare the average to the maximum battery, and if the maximum battery is higher than the average, we use that battery to keep charging some computer, and then we just have to compare the remaining N minus 1 computers with the remaining number of batteries. Keep repeating this process until the maximum amount of power in the remaining batteries is no greater than the average amount of power in the remaining batteries, which means that the remaining batteries are evenly distributed.

answer

class Solution(object):
    def maxRunTime(self, n, batteries):
        """
        :type n: int
        :type batteries: List[int]
        :rtype: int
        """
        if n == 1 : return sum(batteries)
        batteries.sort()
        total = sum(batteries)
        while batteries[-1] > total / n:
            n -= 1
            total -= batteries.pop()
        return total / n
Copy the code

The results

Runtime: 548 ms, faster than 100.00% of Python online submissions for Maximum Running Time of N Computers. Submissions in Python online submissions for Maximum Running Time of N Computers.Copy the code

The original link

Leetcode.com/contest/wee…