本题为2023年5月10日华为暑期实习机考原题

华为机考的介绍点击这里

题目内容

有一个叫做小红的人，他非常喜欢喝茶。他有 $x$ 个奇怪的杯子，每个杯子都可以装入一个正整数。小红决定将这些杯子中的个数字压入一个栈中，但他有些规矩：每次他要向栈中压入一个数字，如果栈顶数字与前一个数字相同，他就会将这两个数字取出来相加，并且将它们的和压入栈中。另外，如果栈顶数字等于栈顶之下连续的 $y$ 个数字的和（$1$ $\leq$ $y$ $\leq$ $x$），他也会将这 $y+1$ 个数字取出来相加，并且将它们的和压入栈中。当然，如果以上两个规则都不满足，他就不会进行任何操作。现在，小红将一组正整数依次压入栈中，请你告诉他最终栈中剩下的数字是什么。

输入描述

使用单个空格隔开的正整数的字符串，如"$5$ $6$ $7$ $8$", 左边的数字先入栈。

正整数的范围为[$1$, $2^{31}-1$]

正整数个数的范围为[$1$,$1000$]。

输出描述

最终栈中存留的元素值，元素值使用的单个空格隔开，如"$8$ $7$ $6$ $5$", 从做至右依次为栈顶至栈底的数字。

样例1

输入

55 66 121 5 5

输出

10 242

解释：向栈压入 $121$ 时，$55$ + $66$ = $121$ ，数据合并后入栈 $242$ ，压入两个 $5$ 时，合并为 $10$ ，最终栈顶至栈底的数字为 $10$ 和 $242$ .

样例2

输入

7 5 8 9 3

输出

3 9 8 5 7

解释：无任何整数合并

问题描述

给定一组正整数 n，我们需要按顺序将这些数字逐个加入栈中。但在每次压入数字时，需要根据以下两种情况进行特殊处理：

1. 条件一：如果当前数字 x 和栈顶元素 y 相同，那么需要取出栈顶元素 y，并将一个新的数字 x + y（即 2 * x）压入栈中。
2. 条件二：如果当前数字 x 和栈顶开始往下的若干个元素（至少 2 个）的和相等，那么需要将这些元素全部取出，并将一个新的数字 2 * x 压入栈中。

流程分析

每次将新数字 x 入栈时，我们需要依次检查栈顶元素，并判断是否满足上述两个条件：

• 检查满足条件 1，我们直接将栈顶元素 y 出栈，并将 2 * x 入栈。
• 检查满足条件 2，我们需要找到栈顶元素开始往下的连续元素，它们的和与当前数字 x 相等，那么这些元素都需要出栈，并将 2 * x 入栈。

特别地，合并后的新数字可能会引发再次合并的操作。比如，当栈中已有 [2, 4, 3] 时，如果我们加入 3，就会触发条件 1（3 == 3），此时我们将 3 出栈并压入 6。然后栈变为 [2, 4, 6]，接着会触发条件 2，因为 2 + 4 = 6，因此我们将 2 和 4 都出栈并压入 12。

思路

我们对于压入栈的每个数$x$，从栈顶开始往栈底逐步求和，检查是否有某个时刻满足$sum = x$ , 如果是这样，将这些元素弹出，然后将他们加起来$x += sum$ 。 此时拿着新的$x$继续进行求和检查 ， 直到无法将$x$和栈顶的若干个元素进行合并，才进入下一次循环处理新的数。整体为三重循环。

时间复杂度

在最坏的情况下，每次压入栈时，我们可能需要遍历栈中的所有元素来判断是否满足条件 2（例如，栈中的元素是一个单调递减的序列）。因此，每次压入栈的时间复杂度是 O(N)，总的时间复杂度是 O(N^2)，其中 N 是给定正整数的数量。

代码

maxn = 1010  # 最大栈大小，足够容纳输入的所有数
stack = [0] * maxn  # 用数组模拟栈，初始化栈的大小为maxn
top = 0  # 栈顶指针，表示栈中最后一个有效元素的位置

arr = list(map(int, input().split()))  # 读取输入的数字并转换为列表

# 遍历输入的每个数
for x in arr:
    # 尝试合并栈内元素直到不满足合并条件
    while True:
        flag = False  # 用来标记是否执行了合并操作
        tmp = 0  # 用来存储当前连续栈内元素的和
        
        # 从栈顶开始向下遍历所有元素
        for i in range(top, -1, -1):
            tmp += stack[i]  # 累加栈中的元素
            
            # 如果当前连续元素的和等于当前的x
            if tmp == x:
                # 合并栈内元素，设置新的x值为当前和的两倍
                x += tmp
                # 更新栈顶，i-1表示将合并的元素出栈
                top = i - 1
                flag = True  # 标记已经合并
                break  # 跳出当前for循环
        
        # 如果没有合并任何元素，跳出while循环
        if not flag:
            break
    
    # 将当前x压入栈中
    top += 1  # 栈顶位置增加
    stack[top] = x  # 将x放入栈顶位置

# 输出栈中的所有元素（从栈顶开始打印）
while top > 0:
    print(stack[top], end=" ")  # 输出栈顶元素
    top -= 1  # 栈顶指针向下移动