电池的寿命(极简版)

解题思路:虽然这道题被划到贪心，但至今没觉得哪里体现了贪心的思想。一开始我用分治的思想：把整个list分成长度不大于3的若干组，计算每组的使用时间和剩余时间，使用时间叠加到总时间tz，然后剩余时间相当于一节新的电池；由这list分成的若干组全部处理完成为一轮，然后这一轮中产生的剩余时间（新电池）又构成新的list进入下一轮，直到list为空或1（即只剩一节电池）。这种思想除了麻烦并没有什么大问题，但有一个不好解决的是如何分组才能达到最优。但回看计算每组使用时间和剩余时间的时候我发现想复杂了，所以以上都是废话。

注意事项:

参考代码:

while 1:
    try:
        N = int(input())
        list = [int(i) for i in input().split()]
        if max(list) > sum(list)-max(list):        # 有剩余情况
            print('{:.1f}'.format(sum(list)-max(list)))
        else:                                      # 无剩余情况
            print('{:.1f}'.format(sum(list)/2))
    except:
        break

def dianchi(lst):   # lst为list的子序列
    t = 0   # 本组使用时间
    s = 0   # 本组剩余时间
    if len(lst) == 1:
        t = 0
        s = lst[0]
    elif len(lst) == 2:
        t = min(lst)
        s = max(lst) - t
    else:
        lst.sort(reverse=True)
        a,b,c = lst[0],lst[1],lst[2]
        if b+c <= a:
            t = b+c
            s = a - t
        else:
            s = 0
            if a == b:
                t = a+ c/2
            else:
                x = (a+b-c)/2
                t = a + (b-x)
    global tz
    tz += t
    if s!=0:
        temp.append(s)

def divide(list):
    if len(list) != 0:
        if len(list) >= 3:
            if len(list) % 3 == 0:
                dianchi(list[:3])
                list[:3] = []
            else:
                dianchi(list[:2])
                list[:2] = []
        else:
            dianchi(list[:len(list)])
            list[:len(list)] = []


while True:
    try:
        N = int(input())
        list = [int(i) for i in input().split()]
        temp = []
        tz = 0    # 总使用时间
        
        while len(list) != 0:
            divide(list)
        
        while 1:
            list = [i for i in temp]
            temp = []
            if len(list) == 0 or len(list) == 1:
                break
            else:
                divide(list)
        
        print('{:.1f}'.format(tz))
    except:
        break