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

preface

I was playing a game with my brother, but suddenly the alarm clock went off at 10:30 PM. It was the alarm clock that reminded me to play my 70th biweekly match, so I turned off the game in a hurry. I felt sorry for my teammates. This is the first question in the Biweekly Contest 70. It’s Easy. It feels like it’s examining greed and sorting arrays.

describe

A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.

  • For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return the minimum cost of buying all the candies.

Example 1:

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: The way in which we can get the minimum cost is described below:
- Buy candies with costs 9 and 7
- Take the candy with cost 6 for free
- We buy candies with costs 5 and 2
- Take the last remaining candy with cost 2 for free
Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.
Copy the code

Note:

1 <= cost.length <= 100
1 <= cost[i] <= 100
Copy the code

parsing

A store is promoting candy. For every two candies sold, the store will give away a third candy for free. Customers can choose any candy to take away for free, but the price of the candy is required to be less than or equal to the minimum price of the two candies purchased.

  • For example, if there are four candies at prices 1, 2, 3, and 4, and the customer buys the candies at prices 2 and 3, they can get the candies at price 1 for free, but not the candies at price 4.

Given an integer array cost with an index of 0, where cost[I] represents the cost of the ith candy, return the lowest cost to buy all the candy.

This problem though investigation is sorting, but also reveal a little bit of greed, because we want to be the lowest cost, then try to get free candy, high price and want to get the candy with high price, just want to buy for the price of the candy is greater than or equal to candy, so the idea of the most simple is to ascending sort an array of cost, We only need to buy the candy from back to front, and the cost of the candy every two times cost. Pop (-1) is included in result, and then we can get one cost. Pop (-1) candy for free until cost is empty, so that we can buy all the candy with the lowest cost.

In general, it’s pretty simple, the time complexity is O(n), the space complexity is O(1).

In fact, WHEN I was doing the first question, I obviously felt that the topic of the two-week competition was not easy, and the following questions proved my idea.

answer

class Solution(object):
    def minimumCost(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        cost.sort()
        result = 0
        count = 0
        while cost:
            result += cost.pop(-1)
            count += 1
            if count == 2 and cost:
                cost.pop(-1)
                count = 0
        return result

        	      
		
Copy the code

The results

192/192 Test cases passed. Status: Accepted Runtime: 28 MS Memory Usage: 13.6 MBCopy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation