空栈压数

题目描述

向一个空栈压入正整数, 每当压入一个整数时, 执行以下规则 (设: 栈顶至栈底整数依次编号为 n1, n2, ..., nx, 其中n1 为最新压入的整数)

1. 如果 n1 = n2, 则 n1/n2全部出栈, 压入新数据 m, m = 2 * n1
2. 如果 n1 = n2 + ... + ny (y的范围为[3, x]), 则 n1, n2, ..., ny 全部出栈, 压入新数据 m, m = 2 * n1.
3. 如果上述规则都不满足, 则不做操作.

例如: 依次向栈压入 6/1/2/3:

• 当压入 2 时, 栈顶至栈底依次为 [2,1,6].
• 当压入 3 时, 3 = 2 + 1, 3/2/1 全部出栈, 重新入栈整数6, 此时栈顶至栈底依次为 [6, 6]; 6 = 6, 两个 6 全部出栈, 压入 12.
• 最终栈中只剩个元素 12.

输入

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

• 正整数大小为 [1, 2^31−1]
• 正整数个数为 [1,1000]

输出

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

示例1

输入:

10 20 50 80 1 1

输出:

2 160

示例2

输入:

5 10 20 50 85 1

输出:

1 170

题解

Python

def main():
    # 读取输入, 并将它们转换成正整数
    # 然后创建一个空的栈
    # 遍历所有的正整数, 依次入栈
    # 每次入栈时做以下检查:
    # 1. 如果 n1=n2, 则它们全出栈, 然后自动入栈 2 * n1
    # 2. 如果 n1=sum(n2, n3..), 则它们全出栈, 然后自动入栈 2 * n1
    # 最后打印栈中剩下的整数

    numbers = list(map(int, input().split()))
    stack = []

    for number in numbers:
        # 检查规则1
        if stack and stack[-1] == number:
            stack[-1] += number
            continue

        top_sum = 0
        will_append = True

        # 从栈顶开始求和
        for i in range(len(stack) - 1, -1, -1):
            top_sum += stack[i]
            if top_sum > number:
                # 不满足
                break
            elif top_sum == number:
                # 满足规则2
                for j in range(len(stack) - 1, i - 1, -1):
                    stack.pop()
                stack.append(number * 2)
                will_append = False
                break

        if will_append:
            # 如果上面的规则不满足, 就把该整数入栈
            stack.append(number)
    # 打印结果
    s = " ".join(map(str, reversed(stack)))
    print(s)

if __name__ == "__main__":
    main()

Rust

use std::cmp::Ordering;
use std::io::{stdin, BufRead};

fn solution() {
    // 读取输入, 并将它们转换成正整数
    // 然后创建一个空的栈
    // 遍历所有的正整数, 依次入栈
    // 每次入栈时做以下检查:
    // 1. 如果 n1=n2, 则它们全出栈, 然后自动入栈 2 * n1
    // 2. 如果 n1=sum(n2, n3..), 则它们全出栈, 然后自动入栈 2 * n1
    // 最后打印栈中剩下的整数

    let mut line = String::new();
    let ret = stdin().lock().read_line(&mut line);
    assert!(ret.is_ok());
    let numbers: Vec<i32> = line
        .split_ascii_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
    let mut stack: Vec<i32> = Vec::new();

    for &number in &numbers {
        // 检查规则1
        if stack.last() == Some(&number) {
            stack.pop();
            stack.push(number * 2);
            continue;
        }

        let mut top_sum = 0;
        let mut will_append = true;

        // 从栈顶开始求和
        for i in (0..stack.len()).rev() {
            top_sum += stack[i];
            match top_sum.cmp(&number) {
                Ordering::Greater => {
                    // 不满足
                    break;
                }
                Ordering::Equal => {
                    // 满足规则2
                    stack.resize(i, 0);
                    stack.push(number * 2);
                    will_append = false;
                    break;
                }
                _ => (),
            }
        }

        if will_append {
            // 如果上面的规则不满足, 就把该整数入栈
            stack.push(number);
        }
    }

    // 打印结果
    let out = stack
        .into_iter()
        .rev()
        .map(|x| x.to_string())
        .collect::<Vec<_>>()
        .join(" ");
    println!("{out}");
}

fn main() {
    solution();
}