E卷-空栈压数(100分)

空栈压数

问题描述

向一个空栈压入正整数，每当压入一个整数时，执行以下规则（设：栈顶至栈底整数依次编号为 ，其中 为最新压入的整数）：

1. 如果 ，则 、 全部出栈，压入新数据 ()。
2. 如果 ( 的范围为 )，则 全部出栈，压入新数据 ()。
3. 如果上述规则都不满足，则不做操作。

向栈中输入一串数字，请输出应用此规则后栈中最终存留的数字。

输入格式

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

输出格式

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

样例输入

10 20 50 80 1 1

样例输出

2 160

样例解释

解释：向栈压入 80 时，10+20+50=80，数据合并后入栈 160，压入两个 1 时，合并为 2，最终栈顶至栈底的数字为 2 和 160。

样例输入

5 10 20 50 85 1

样例输出

1 170

数据范围

• 正整数大小为 。
• 正整数个数为 。

题解

这道题的核心在于模拟栈的操作和数字合并的过程。解题思路如下：

1. 使用一个列表来模拟栈的操作。
2. 对于每个输入的数字，尝试将其与栈中已有的数字进行合并。
3. 合并过程从栈顶开始，逐个累加栈中的数字，直到找到满足条件的组合或无法继续合并。

关键点在于理解合并的规则：

• 如果新数字等于栈顶的数字，直接合并这两个数字。
• 如果新数字等于栈顶若干个数字的和，合并这些数字。
• 合并后的新数字是原数字的两倍。

例如，考虑输入 "10 20 50 80 1 1"：

1. 压入 10、20、50：栈变为 [50, 20, 10]
2. 压入 80：80 = 50 + 20 + 10，合并为 160，栈变为 [160]
3. 压入 1、1：两个 1 合并为 2，栈最终变为 [2, 160]

参考代码

• Python

def push(num, stack):
    """
    将新数字压入栈中，并尝试进行合并
    :param num: 要压入的新数字
    :param stack: 当前的栈
    """
    total = num
    
    # 从栈顶开始，尝试合并数字
    for i in range(len(stack)-1, -1, -1):
        total -= stack[i]
        
        # 如果找到了可以合并的组合
        if total == 0:
            # 移除被合并的数字
            del stack[i:]
            # 将合并后的新数字压入栈中
            push(num * 2, stack)
            return
        # 如果和变成负数，说明无法合并，退出循环
        elif total < 0:
            break
    
    # 如果无法合并，直接将新数字压入栈顶
    stack.append(num)

# 读取输入
nums = list(map(int, input().split()))

# 初始化栈，将第一个数字压入
stack = [nums[0]]

# 处理剩余的数字
for i in range(1, len(nums)):
    push(nums[i], stack)

# 反转栈，使得输出从栈顶到栈底
stack.reverse()

# 输出结果
print(" ".join(map(str, stack)))

• C

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1000

void push(int num, int* stack, int* top) {
    int total = num;
    int i;
    
    // 从栈顶开始，尝试合并数字
    for (i = *top - 1; i >= 0; i--) {
        total -= stack[i];
        
        // 如果找到了可以合并的组合
        if (total == 0) {
            // 移除被合并的数字
            *top = i;
            // 将合并后的新数字压入栈中
            push(num * 2, stack, top);
            return;
        }
        // 如果和变成负数，说明无法合并，退出循环
        else if (total < 0) {
            break;
        }
    }
    
    // 如果无法合并，直接将新数字压入栈顶
    stack[(*top)++] = num;
}

int main() {
    int stack[MAX_SIZE];
    int top = 0;
    int num;
    
    // 读取输入
    while (scanf("%d", &num) != EOF) {
        push(num, stack, &top);
    }
    
    // 输出结果（从栈底到栈顶）
    for (int i = top - 1;