Python 买二赠一 蓝桥杯2023年第14届省赛 (dotcpp:3175) 贪心思路解决

题目描述
某商场有 N 件商品，其中第 i 件的价格是 Ai。现在该商场正在进行 “买二赠一” 的优惠活动，具体规则是：
每购买 2 件商品，假设其中较便宜的价格是 P（如果两件商品价格一样，则 P 等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过 P/2的商品，免费获得这一件商品。可以通过反复购买 2 件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。
小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？

输入格式
第一行包含一个整数 N。
第二行包含 N 个整数，代表 A1, A2, A3, . . . ，AN。
输出格式
输出一个整数，代表答案。
样例输入
7
1 4 2 8 5 7 1
样例输出
25

最贵的商品是无法免单的，所以思路大概是贪心，先选最贵的，然后查找要免单的那一个
排序得{1 1 2 4 5 7 8}。先购买最贵的8、7，然后可以免单的最贵的是2。再购买剩下的最贵的5、4，免单1。最后单独买1。总价是25。

第一次的思路：
查找的时候速度太慢了，所以lanqiao上面有3个例子 超时了

import os
import sys

n = int(input())
a = list(map(int, input().split()))

a.sort()
length = len(a)
m = [1] * length # 标记list
sum_price = 0 # 总金额
last = -1 # 从大到小，依次标记最后一个值
cnt = 0 # 每两个就要找可以免单的
for i in range(length - 1, -1, -1):
    if m[i] != 0:
        sum_price += a[i]
        last = a[i]
        cnt += 1
        m[i] = 0 # 标记变为 0
    if cnt == 2:
        cnt = 0
        for j in range(i,-1,-1):
            if int(last // 2) >= a[j] and m[j] != 0:
                m[j] = 0
                # print('**',a[j])
                break
print(sum_price)

在原来基础上添加二分查找，因为是顺序表，所以可以用二分查找，新代码，在dotcpp上就可以通过，在lanqiao上面通过80% 我也不太理解

def search(a, left, right, s):
    while(left < right):
        mid = left + (right - left) // 2
        if a[mid] >= s:
            right = mid 
        else:
            left = mid + 1
    return left


n = int(input())
a = list(map(int, input().split()))

a.sort()
length = len(a)
m = [1] * n # 标记list, 如果为0 则表示已经选择过了
sum_price = 0 # 总金额
last = -1 # 从大到小，依次标记最后一个值
cnt = 0 # 每两个就要找可以免单的
last_id = n - 1
for i in range(length - 1, -1, -1):
    if m[i] != 0:
        sum_price += a[i]
        last = a[i]
        cnt += 1
        m[i] = 0
    if cnt == 2:
        cnt = 0
        x = search(a, 1, last_id, last // 2)
        # 找到一个符合免单的元素，
        if m[x] == 0 or a[x] > last // 2 :
            x -= 1
        if m[x] != 0:
            m[x] = 0
            last_id = x - 1
print(sum_price)