鱼C论坛Python精英挑战赛（第四季02期）

jerryxjr1220

第四届鱼C论坛精英挑战赛即将回归咯！为了增加趣味性，本届仍然延续“新玩法”-- “押宝玩法”，“竞猜玩法”和“擂主玩法”。

同时，根据以往鱼油的反馈，精英赛题目普遍偏难，所以参与的鱼油相对较少。为了提高大家的参与度，本届挑战赛会大幅降低难度，使大部分鱼油都能参赛。同时，会增设一、二、三名奖励，第一名奖励50鱼币，第二名30鱼币，第三名20鱼币。

新玩法规则：

1. 押宝玩法：由于押宝玩法参与人数很少，故暂停押宝。后续有改进玩法，会再公布。

2. 竞猜玩法：直接在比赛帖的下方进行投票，凡事“竞赛”获胜者，将奖励5鱼币。竞猜无门槛，人人都可以参与。竞猜以后，请在本帖留个言，方便领取奖励。

3. 擂主玩法：上一期挑战成功的鱼油成为挑战赛的擂主，擂主有优先权提议下一期的赛题，一届挑战赛共分5期，同一届中当擂主最长的鱼油有额外奖励。

本期题目： 可收集的最大雨水量

有一片高低起伏的洼地，洼地的海拔高度用一个列表表示，例如：[0,1,0,2,1,0,1,3,2,1,2,1]，其中每个数值代表一小块洼地的高度，每一小块洼地的宽度都是1，在洼地的凹槽处可以储存雨水，如图中蓝色部分表示可收集的雨水，黑色部分为洼地的泥土。

在这样一片洼地中，最大可收集的雨水量是6，所以程序应当返回6，若无法收集雨水，则返回0.

求给定列表中可收集的最大雨水量。

def max_rainwater(list_of_number):
    '''your code here'''
    return result_of_max_rainwater

要求： 结果正确，程序效率高，代码简洁

注：给定的列表长度可能会达到1000或以上，请注意运算效率

截止日期： 12月4日24时

本期擂主： gunjang  由于本期只有算法题，所以就不给选择了

@小甲鱼 @冬雪雪冬 @～风介～ @SixPy

我用Excel写了个算法，画了张图表，希望给大家一些思路。


提供几组测试数据及答案，可以自行对照：
11        20        62        6        15        87        27        50        98        52        55        16        48        38        80        80        85        80        7        58        52        4        68        99        29        42        2        1        61        88          #答案1154
82        64        94        44        8        56        31        29        37        34        54        66        14        43        82        96        44        60        62        70        26        56        60        61        4        74        32        6        77        51        #答案1017
6        53        57        39        90        87        28        95        15        6        63        8        28        93        86        56        28        93        34        71        87        31        67        87        70        2        34        27        6        76        #答案923

竞猜：回答正确的参赛者的人数

蓝色王魂

目前只能想出这个方法，效率还行，但是代码丑。是分别计算每层的水洼面积再累加的。

def max_rainwater(list_of_number):
    result_of_max_rainwater = 0
    length = len(list_of_number)
    max_of_list = max(list_of_number)
    for times in range(max_of_list):
        for i in range(length):
            if list_of_number[i]>0:
                list_of_number[i] -= 1
                start = i
                break
        for i in range(start+1,length):
            if list_of_number[i] > 0:
                list_of_number[i] -= 1
                distance = i-start-1
                start = i
                if distance>0:
                    result_of_max_rainwater += distance
    return result_of_max_rainwater

SylarPu

def max_rainwater(l):
    mwater=0
    i=0
    while i<len(l)-1:
        if l[i+1]>=l[i]:
            i+=1
            continue
        m=0
        for j in range(i+1,len(l)):
            if l[j]<l[i]:
                m+=+l[i]-l[j]
            else:
                i=j
                break
        if i==j:
            mwater+=m
            continue
        i+=1
    return mwater

Elastcio

def max_rainwater(list_of_number):
    i = max(list_of_number)
    total_white = 0
    temp = len(list_of_number)*max(list_of_number) - sum(list_of_number)
    while i>=1:
        total_white += list_of_number.index(max(list_of_number)) + list_of_number[::-1].index(max(list_of_number))
        list_of_number = [x-1 if x == max(list_of_number)  else x  for x in list_of_number]
        i -=1
    print(temp- total_white ) 

>>> max_rainwater([1,2,3])
0
>>> max_rainwater([11,20,62,6,15,87,27,50,98,52,55,16,48,38,80,80,85,80,7,58,52,4,68,99,29,42,2,1,61,88])
1154
>>> max_rainwater([82,64,94,44,8,56,31,29,37,34,54,66,14,43,82,96,44,60,62,70,26,56,60,61,4,74,32,6,77,51])
1017
>>> max_rainwater([6,53,57,39,90,87,28,95,15,6,63,8,28,93,86,56,28,93,34,71,87,31,67,87,70,2,34,27,6,76])
923
'''

shuo

def max_rain(lst):
        rain = 0
        lst2 = lst[:]
        while True:
                fn = max(lst)
                fi=lst.index(fn)

                lst1 = lst[:fi]
                if len(lst1) == 1 :
                        break
                else:
                        sn = max(lst1)
                        si = lst1.index(sn)
                        for i in range (si,fi):
                                rain += sn - lst[i]
                        if len(lst1) == 2:
                               break
                        else:
                               lst = lst1
        while True:
                fn = max(lst2)
                fi = lst2.index(fn)

                lst1 = lst2[fi+1:]
                if len(lst1) <= 1 :
                        break
                else:
                        sn = max(lst1)
                        si = lst1.index(sn)
                        if si == 0:
                                lst2 = lst1[:]
                                continue
                        else:
                                for i in range(si):
                                        rain += sn - lst1[i]
                                lst2 = lst1[si+1:]
                                if len(lst2) == 0:
                                        break

        return rain

gunjang

幸好看了测试。。。否则就出错了，要考虑特殊情况。。。

#http://bbs.fishc.com/thread-100583-1-1.html
t1 = [0,1,0,2,1,0,1,3,2,1,2,1]
t2=[11,20,62,6,15,87,27,50,98,52,55,16,48,38,80,80,85,80,7,58,52,4,68,99,29,42,2,1,61,88]#答案1154
#          ^ 103  ^   97    ^          649                             ^     305      ^ =1154

t3=[82,64,94,44,8,56,31,29,37,34,54,66,14,43,82,96,44,60,62,70,26,56,60,61,4,74,32,6,77,51]#答案1017
t4=[6,53,57,39,90,87,28,95,15,6,63,8,28,93,86,56,28,93,34,71,87,31,67,87,70,2,34,27,6,76]#答案923
def max_rainwater(list_of_number):
        result_of_max_rainwater = 0
        index1 = 0
        while True:
                while (index1+1 < len(list_of_number)) and (list_of_number[index1+1] >= list_of_number[index1]):
                        index1 += 1
                if index1 >= len(list_of_number)-1:
                        break
                H1 = list_of_number[index1]
                j = index1+1
                clayArea = 0
                while (j < len(list_of_number)) and (H1 > list_of_number[j]):
                        clayArea += list_of_number[j]
                        j += 1
                if j < len(list_of_number):
                        #print(index1, j, (j-index1-1)*H1 - clayArea)
                        result_of_max_rainwater += (j-index1-1)*H1 - clayArea
                else:
                        return result_of_max_rainwater + max_rainwater(list_of_number[len(list_of_number):index1-1:-1])
                index1 = j

        return result_of_max_rainwater

print(max_rainwater(t1)) #6
print(max_rainwater(t2))#答案1154
print(max_rainwater(t3))#答案1017
print(max_rainwater(t4))#答案923

qwc3000

"""
解题思路
1、找最大值及位置
2、按照最大值 分段列表，将列表分为3类，一、逐渐上升的到最大值型； 二、以最大值为两端凹坑性；三、以最大值逐渐下降的
3、上升及凹型 求和
4、下降型 翻转  按照上升型求和
5、
"""
def list_max(P_list):
    temp_max_num=0  #最大值
    temp_max_i=0  #最大值最后出现的位置
    list_type=1
    temp=len(P_list)
    for i in range(temp):
        #如果 大于 那么max_num赋值，重新统计位置列表
        if P_list[i]>temp_max_num:
            temp_max_num=P_list[i]
            temp_max_i=i
        elif P_list[i]==temp_max_num:  #如果 等于  增加位置列表
            temp_max_i = i
    # 判断数列整体走向
    if temp_max_i<temp and temp_max_i>0: #混合型
        list_type=2
    elif temp_max_i==0: #下降型
        list_type=3
    elif temp_max_i==temp: #上升型
        list_type=1
    # print("最大值：",temp_max_num,"位置：",temp_max_i,"类型：",list_type)
    return temp_max_num,temp_max_i,temp,list_type#返回 最大值和位置 走向
# 分解
def list_FJ(P_list):
    L_r_tuple=list_max(P_list) # 获取相关内容
    print(L_r_tuple)
    # 对列表进行切片
    temp_list = []
    if L_r_tuple[3]==2: #混合时
        temp_list.append(P_list[:L_r_tuple[1]+1])
        temp_list.append(P_list[L_r_tuple[1]:])
    else: #单一 上升或者下降时
        temp_list=P_list
    return temp_list,L_r_tuple[3]
# 统计计算方法  适合上升 凹型
def total_result12(P_list):
    temp=0
    result_num=0
    for i in range(len(P_list)):
        if temp > P_list[i]:         #
            result_num=result_num+temp-P_list[i]
        else:
            temp=P_list[i]
    return result_num
# 统计计算方法2 适合下降型
def total_result3(P_list):
    P_list.reverse() #反向
    result=total_result12(P_list)
    return result
# P_list 分解后的列表
# P_type 元列表的类型
def total_list(P_list,P_type):
    temp=len(P_list)
    result=0
    if P_type==2:
        for i in range(temp-1):
            result=result+total_result12(P_list[i])
        result=result+total_result3(P_list[temp-1])  # 下降型 反向后
    elif P_type==1:
        result=result+total_result12(P_list[0])
    elif P_type==3:
        result = result + total_result3(P_list(temp - 1))  # 下降型 反向后
    return result
def max_rainwater(list_of_number):
    temp_tuple = list_FJ(list_of_number)
    result_of_max_rainwater = total_list(temp_tuple[0], temp_tuple[1])
    return result_of_max_rainwater
list1=[6,53,57,39,90,87,28,95,15,6,63,8,28,93,86,56,28,93,34,71,87,31,67,87,70,2,34,27,6,76]
#对列表进行分解，得到此列表类型，和分解后的列表
print(max_rainwater(list1))

大月饼

def max_rainwater(list_of_number):
    result_of_max_rainwater = 0
    left_max = list_of_number[0]
    right_max = max(list_of_number[2:])
    for i in range(len(list_of_number)-2):
        if left_max<list_of_number[i]:
            left_max=list_of_number[i]
        if right_max == list_of_number[i+1]:
            right_max = max(list_of_number[i+2:])
        max_lr = left_max if left_max < right_max else right_max
        if max_lr>list_of_number[i+1]:
            result_of_max_rainwater += max_lr-list_of_number[i+1]
    return result_of_max_rainwater

蓝色王魂

两种优化方式，方法都是是积水后的面积减原来的面积，如果都大于一个较大的数，比如说都大于10000，第一种方法效率就会很低，或者如果对与list(set(list_of_number)),相邻的值都差个2，3之类的，第一个方法效率也会变低，但如果数字是从0到最大值基本上每个都有取到的话，第一种方法会稍快。

def max_rainwater2(list_of_number):
    max_value = max(list_of_number)
    sum_all = sum(list_of_number)
    length = len(list_of_number)
    sum_watered = 0
    for i in range(1,max_value+1):
        for j in range(length):
            if list_of_number[j] >= i:
                start = j
                break
        for j in range(length-1,-1,-1):
            if list_of_number[j] >= i:
                end = j
                break
        sum_watered += end - start + 1
    return (sum_watered-sum_all)

def max_rainwater3(list_of_number):
    sum_all = sum(list_of_number)
    sum_watered = 0
    value_list = list(set(list_of_number))
    length = len(list_of_number)
    shuiwei = 0
    for each in value_list:
        for i in range(length):
            if list_of_number[i] >= each:
                start = i
                break
        for i in range(length-1,-1,-1):
            if list_of_number[i] >= each:
                end = i
                break
        sum_watered += (each-shuiwei) * (end - start + 1)
        shuiwei = each
    return (sum_watered-sum_all)

蓝色王魂

最终版

def max_rainwater4(list_of_number):
    sum_watered = max(list_of_number)
    sum_all = sum(list_of_number)
    max_index = list_of_number.index(sum_watered)
    shuiwei = list_of_number[0]
    start = 0
    length = len(list_of_number)
    for i in range(1,max_index+1):
        if list_of_number[i] >= shuiwei:
            sum_watered += shuiwei*(i-start)
            start = i
            shuiwei = list_of_number[i]
    shuiwei = list_of_number[-1]
    start = length - 1
    for i in range(length-2,max_index-1,-1):
        if list_of_number[i] >= shuiwei:
            sum_watered += shuiwei*(start - i)
            start = i
            shuiwei = list_of_number[i]
    return (sum_watered-sum_all)

凌九霄

A = [11, 20, 62, 6, 15, 87, 27, 50, 98, 52, 55, 16, 48, 38, 80, 80, 85, 80, 7, 58, 52, 4, 68, 99, 29, 42, 2, 1, 61, 88]
B = [82, 64, 94, 44, 8, 56, 31, 29, 37, 34, 54, 66, 14, 43, 82, 96, 44, 60, 62, 70, 26, 56, 60, 61, 4, 74, 32, 6, 77, 51]
C = [6, 53, 57, 39, 90, 87, 28, 95, 15, 6, 63, 8, 28, 93, 86, 56, 28, 93, 34, 71, 87, 31, 67, 87, 70, 2, 34, 27, 6, 76]

import random
import timeit

D = [random.randint(1, 99) for i in range(1000)]
E = [random.randint(1, 1000) for i in range(1000000)]


def max_rainwater(lst):
    maxvalue = max(lst)
    ABsection = (lst[:lst.index(maxvalue) + 1], lst[lst.index(maxvalue):][::-1])
    result = 0
    for i in ABsection:
        bigvalue = i[0]
        for j in range(1, len(i)):
            if i[j] >= bigvalue:
                bigvalue = i[j]
            else:
                result += bigvalue - i[j]

    return result, lst


rw = max_rainwater(A)
print('列表长度：{0}  可收集最大雨水数：{1}'.format(len(rw[1]), rw[0]))
rw = max_rainwater(B)
print('列表长度：{0}  可收集最大雨水数：{1}'.format(len(rw[1]), rw[0]))
rw = max_rainwater(C)
print('列表长度：{0}  可收集最大雨水数：{1}\n'.format(len(rw[1]), rw[0]))

rw = max_rainwater(D)
print('随机列表长度：{0}  可收集最大雨水数：{1}'.format(len(rw[1]), rw[0]))
print('函数执行用时：{0}s\n'.format(timeit.timeit('max_rainwater(D)', setup='from __main__ import max_rainwater,D', number=1)))

rw = max_rainwater(E)
print('随机列表长度：{0}  可收集最大雨水数：{1}'.format(len(rw[1]), rw[0]))
print('函数执行用时：{0}s'.format(timeit.timeit('max_rainwater(E)', setup='from __main__ import max_rainwater,E', number=1)))

城管熙

def jishui(x):
    t=time.time()
    water=0
    for k in range(max(x)):
        y=[]
        for i in range(len(x)):
            if x[i]>=max(x)-k:
                y.append(i)
        if len(y)>=2:
            water=water+y[(len(y)-1)]-y[0]-len(y)+1
    t1=time.time()
    print(t1-t)
            
    return water
c=[11,20,62,6,15,87,27,50,98,52,55,16,48,38,80,80,85,80,7,58,52,4,68,99,29,42,2,1,61,88]
print(jishui(c))

城管熙

def jishui(x):
    t=time.time()
    water=0
    for k in range(max(x)):
        y=[]
        for i in range(len(x)):
            if x[i]>=max(x)-k:
                y.append(i)
        if len(y)>=2:
            water=water+y[(len(y)-1)]-y[0]-len(y)+1
    t1=time.time()
    print(t1-t)
            
    return water
c=[11,20,62,6,15,87,27,50,98,52,55,16,48,38,80,80,85,80,7,58,52,4,68,99,29,42,2,1,61,88]
print(jishui(c))

城管熙

怎么发有行数的代码

Pythonbn

def max_rain(lst):
        rain = 0
        lst2 = lst[:]
        while True:
                fn = max(lst)
                fi=lst.index(fn)

                lst1 = lst[:fi]
                if len(lst1) == 1 :
                        break
                else:
                        sn = max(lst1)
                        si = lst1.index(sn)
                        for i in range (si,fi):
                                rain += sn - lst[i]
                        if len(lst1) == 2:
                               break
                        else:
                               lst = lst1
        while True:
                fn = max(lst2)
                fi = lst2.index(fn)

                lst1 = lst2[fi+1:]
                if len(lst1) <= 1 :
                        break
                else:
                        sn = max(lst1)
                        si = lst1.index(sn)
                        if si == 0:
                                lst2 = lst1[:]
                                continue
                        else:
                                for i in range(si):
                                        rain += sn - lst1[i]
                                lst2 = lst1[si+1:]
                                if len(lst2) == 0:
                                        break

        return rain