大鱼吃小鱼的python代码

Question

介绍。
你对编码感到非常厌烦。于是你决定去河岸边坐一坐，让自己的头脑清醒一下。过了一会儿，你注意到在河里有两群鱼朝相反的方向游，一个顺着河水流向，另一个逆着河水流向。令人惊讶的是，当来自不同鱼群的两条鱼相遇时，按重量计算，较大的那条鱼会吃掉较小的那条，并保持其方向。这种有趣的现象一直持续到两派之间没有相遇为止。
给出两个整数的重量和方向的列表，你的任务是计算河中剩余的鱼的数量。
输入：（输入这些变量的代码已经为你完成了）

• weight 一个整数的列表，代表河中鱼类的大小。
• directions - 一个{0,1}的列表，代表鱼群的行进方向，0是逆流而上，1是顺流而下。我们假设河水从左向右流，鱼群以相同的恒定速度游动（两条在同一方向游动的鱼永远不会相遇）。

例子。
假设我们得到的权重=[4, 3, 2, 1, 5]，方向=[0, 1, 0, 0, 0] 。
从输入中，我们看到第一条鱼重4个单位，逆流而行（从右到左），而第二条鱼重3个单位，向右行驶。很明显，鱼-1和鱼-2永远不会相遇。然而，鱼-2最终会与鱼-3相遇，当相遇时，由于鱼-3的体积较大，它将吃掉鱼-3。鱼-2将继续沿以前的方向移动。它将再次在某个时间点与鱼-4相遇，这时它将吃掉鱼-4。有趣的是，当鱼-2继续它的路线时，它会遇到鱼-5。但这一次鱼-5将占上风。
最后，鱼-1和鱼-5在同一方向游动，永远不会相遇，它们是这场激烈的自然选择的幸存者。
在这种情况下，剩下的鱼的数量是2。
测试案例。
输入
50 4 1 2 6
01000
输出 2

class Fish:
    def __init__(self, weight, direction):
        self.weight = weight
        self.direction = direction

def solve(fishes):

#在这上面输入你的代码
def main():
    weights = list(map(int, input().split()))
    directions = list(map(int, input().split()))

    fishes = []
    for i in range(len(weights)):
        fishes.append(Fish(weights[i], directions[i]))

    print(solve(fishes))

if __name__ == "__main__":
    main()

Answer 1

基于Monster 组和GPT的调写：

• 用栈的数据结构，从左到右遍历每条鱼入栈，如果当前鱼的方向是逆流而上，也就是0，那么会与栈中的鱼进行比较，如果它比栈顶的鱼重，栈顶的鱼出栈，直到么有比当前鱼更小的鱼或栈为空为止，然后当前鱼入栈。遍历完所有鱼之后，栈中剩余的鱼就是剩下的鱼的数量。

代码实现：

class Fish:
    def __init__(self, weight, direction):
        self.weight = weight
        self.direction = direction

def solve(fishes):
    stack = []

    for fish in fishes:
        if fish.direction == 1:
            stack.append(fish)
        else:
            while stack and stack[-1].direction == 1 and stack[-1].weight < fish.weight:
                stack.pop()
            if not stack or stack[-1].direction == 0:
                stack.append(fish)

    return len(stack)

def main():
    weights = list(map(int, input().split()))
    directions = list(input().strip())

    fishes = []
    for i in range(len(weights)):
        fishes.append(Fish(weights[i], int(directions[i])))

    print(solve(fishes))

if __name__ == "__main__":
    main()