当前位置:网站首页>Leetcode simple question: the minimum cost of buying candy at a discount
Leetcode simple question: the minimum cost of buying candy at a discount
2022-07-05 22:02:00 【·Starry Sea】
subject
A shop is selling candy at a discount . Every time you buy Two candy , Shop meeting free Send a candy .
The only restriction on free candy is : Its price needs to be less than or equal to the price of two candies purchased Smaller value .
For example , All in all 4 A candy , The prices are 1 ,2 ,3 and 4 , A customer bought it for 2 and 3 Of candy , Then he can get the price for free 1 Of candy , But you can't get a price of 4 Of candy .
I'll give you a subscript from 0 The starting array of integers cost , among cost[i] It means the first one i The price of a candy , Please return to get all Candy Minimum The total cost .
Example 1:
Input :cost = [1,2,3]
Output :5
explain : Our purchase price is 2 and 3 Of candy , Then get the price for free 1 Of candy .
The total cost is 2 + 3 = 5 . This is the least expensive only programme .
Be careful , We can't buy at 1 and 3 Of candy , And get the price for free 2 Of candy .
This is because the price of free candy must be less than or equal to the purchase 2 The smaller value of the candy price .
Example 2:
Input :cost = [6,5,7,9,2,2]
Output :23
explain : The minimum total cost of buying candy is :
- The purchase price is 9 and 7 Of candy
- The free price is 6 Of candy
- The purchase price is 5 and 2 Of candy
- The free price is 2 The last candy of
therefore , The minimum total cost is 9 + 7 + 5 + 2 = 23 .
Example 3:
Input :cost = [5,5]
Output :10
explain : Because only 2 A candy , We need to buy them all , And there is no free candy .
So the total minimum cost is 5 + 5 = 10 .
Tips :
1 <= cost.length <= 100
1 <= cost[i] <= 100
source : Power button (LeetCode)
Their thinking
For a given cost, The maximum value and the second largest value will definitely not be given , Then if the third largest value exists, it will be given away , So you can cost Sort from large to small , Then take out the first three values for operation , The remaining subsequence is another round of operation .
class Solution:
def minimumCost(self, cost: List[int]) -> int:
s=0
cost.sort(reverse=True)
for i in range(len(cost)):
if (i+1)%3!=0: # The third largest value does not need to be included in the total price
s+=cost[i]
return s
边栏推荐
- Huawei game multimedia service calls the method of shielding the voice of the specified player, and the error code 3010 is returned
- Performance monitoring of database tuning solutions
- "Chris Richardson microservices series" uses API gateway to build microservices
- Win11运行cmd提示“请求的操作需要提升”的解决方法
- Recovery technology with checkpoints
- Form artifact
- DBeaver同时执行多条insert into报错处理
- datagrid直接编辑保存“设计缺陷”
- Oracle views the data size of a table
- Granularity of blocking of concurrency control
猜你喜欢
Create a virtual machine on VMware (system not installed)
从零开始实现lmax-Disruptor队列(四)多线程生产者MultiProducerSequencer原理解析
AD637 usage notes
微服务入门(RestTemplate、Eureka、Nacos、Feign、Gateway)
MMAP learning
Reptile practice
华为云ModelArts文本分类–外卖评论
Implementation technology of recovery
PIP install beatifulsoup4 installation failed
Defect detection - Halcon surface scratch detection
随机推荐
华为联机对战如何提升玩家匹配成功几率
Summary of concurrency control
Server optimization of performance tuning methodology
A trip to Suzhou during the Dragon Boat Festival holiday
Getting started with microservices (resttemplate, Eureka, Nacos, feign, gateway)
Meituan dynamic thread pool practice ideas, open source
Efficiency difference between row first and column first traversal of mat data types in opencv
NET中小型企业项目开发框架系列(一个)
Poj3414广泛搜索
HYSBZ 2243 染色 (树链拆分)
MMAP
C language knowledge points link
数博会精彩回顾 | 彰显科研实力,中创算力荣获数字化影响力企业奖
Create a virtual machine on VMware (system not installed)
[Yugong series] go teaching course in July 2022 004 go code Notes
大约SQL现场“这包括”与“包括在”字符串的写法
【愚公系列】2022年7月 Go教学课程 004-Go代码注释
Interprocess communication in the "Chris Richardson microservice series" microservice architecture
Summarize the reasons for 2XX, 3xx, 4xx, 5xx status codes
Performance monitoring of database tuning solutions