计算题

[编程题]计算题

热度指数：2974 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定n个非负整数表示每个宽度为1的柱子的高度题，计算按此排列的柱子，下雨之后能接多少雨水。

输入描述:

逗号分隔的整数，表示每根柱子的高度。
柱子数n<=1000000,每根柱子的高度不大于100000

输出描述:

雨水量（高度和）

示例1

输入

0,1,0,2,1,0,1,3,2,1,2,1

输出

算法知识视频讲解

Python

ElonB

""""
特殊的单调递增
序列a按照最高值划分为两个数组b、c，后半部分翻转
对每一个数组，遍历数组，
若当前最大值t_max小于x，则更新t_max = x；
若大于，则计数 t_max - x
"""


def count(a):
    ret, t_max = 0, 0
    for x in a:
        if x > t_max:
            t_max = x
        else:
            ret += t_max - x
    return ret


if __name__ == "__main__":
    a = list(map(int, input().strip().split(',')))
    b = a[a.index(max(a)):][::-1]
    c = a[:a.index(max(a)) + 1]
    ans = 0
    ans += count(b)
    ans += count(c)
    print(ans)

发表于 2019-07-14 18:44:02 回复(0)