首页 > 试题广场 >

香槟塔

[编程题]香槟塔

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

节日到啦，牛牛和妞妞邀请了好多客人来家里做客。
他们摆出了一座高高的香槟塔，牛牛负责听妞妞指挥，往香槟塔里倒香槟。
香槟塔有个很优雅的视觉效果就是如果这一层的香槟满了，就会从边缘处往下一层流去。
妞妞会发出两种指令，指令一是往第x层塔内倒体积为v的香槟，指令二是询问第k层塔香槟的体积为多少。

告诉你香槟塔每层香槟塔的初始容量，你能帮牛牛快速回答妞妞的询问吗？

输入描述:

第一行为两个整数n，m。表示香槟塔的总层数和指令条数。
第二行为n个整数a_i，表示每层香槟塔的初始容量。
第三行到第2+m行有两种输入，一种输入是“2 x v”表示往第x层倒入体积为v的香槟；另一种输入是“1 k”表示询问第k层当前有多少香槟。
1 <= n, m <= 1000。
1 <= n ,m <= 200000，1 <= ai ,v <= 1000000000。

输出描述:

对于每个询问，输出一个整数，表示第k层香槟的容量。

示例1

输入

输出

示例2

输入

输出

0
4

算法知识视频讲解

Python

Ning111

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
b = [0 for i in range(n)] for i in range(m):
    order = [int(j) for j in input().split()]  if order[0] == 1:  print(b[order[1]-1])  else:
        k = 0   while b[order[1]+k-1]+order[2] > a[order[1]+k-1] and order[1]+k < n:
            order[2] = order[2] - (a[order[1]+k-1]-b[order[1]+k-1])
            b[order[1]+k-1] = a[order[1]+k-1]
            k += 1   b[order[1] + k-1] += min(order[2], (a[order[1]+k-1]-b[order[1] + k-1]))

发表于 2019-09-06 22:33:30 回复(0)

Python

意识流选手

Python Solution
假设第 $i$ 层初始状态值为 $-a_i$ ，则装满的情况为该层状态值达到 $0$ 。

假如第1层容积为2，则初始状态值为-2，倒入体积3的酒，则状态值归0，剩余体积1的酒向下流动。

n, m = [int(i) for i in  input().split()]
a = [int(i) for i in input().split()]
st = [-i for i in a]
all_ml = [[int(i) for i in input().split()] for i in range(m)]


def pour(st, ml):
    '''香槟塔的第x层到体积v的酒'''
    x = ml[1]-1
    v = ml[2]
    while True:
        v = v + st[x]
        if v < 0:
            st[x] = v
            break
        else:
            st[x] = 0
            x += 1
            if x == len(st):
                break
    return st

def ask(a, st, ml):
    '''k层装酒量=k层容积+k层状态值'''
    k = ml[1]
    print(a[k-1]+st[k-1])


for ml in all_ml:
    if ml[0] == 2:
        st = pour(st, ml)
    else:
        ask(a, st, ml)

编辑于 2019-08-28 15:53:44 回复(0)