2023.05.10-暑期实习-第一题-塔子哥的茶杯

XiangChao LV 3 @ 8 months ago

nums = list(map(int, input().split()))
st = []

for num in nums:
    if (not st) or (num < st[-1]):
        st.append(num)
    elif num == st[-1]:
        st[-1] = num * 2
        i = len(st) - 1
        while i >= 0 and len(st) >= 2:
            if st[i] == st[i-1]:
                st.pop()
                st[-1] *= 2
                i = len(st) - 1
            else:
                break
    else:
        tmp = 0
        flag = True
        for i in range(len(st)-1, -1, -1):
            tmp += st[i]
            if num == tmp:
                st = st[:i] + [num*2]
                break
            elif num < tmp:
                flag = False
                break
            else:
                continue
        if (not flag) or (tmp < num):
            st.append(num)

st = st[::-1]
st = [str(x) for x in st]
print(" ".join(st))

TaZi SU @ 8 months ago

思路：模拟栈

什么是栈？

栈是一个先进后出的容器，你可以理解为一个只有一边能够打开的羽毛球筒，那我们想把最里面的羽毛球取出来，就得把所有羽毛球都取出来，这就是栈。

我们需要将给出的 $n$ 个正整数逐一加入到栈中，但是在每次入栈时，如果我们发现有以下两种情况，就需要做出相应的操作：

当前数 $x$ 和栈顶 $y$ 是同一个数，那么我们需要取出栈顶数 $y$ ，并将一个新的数 $x+y$ 或者说是 $2*x$ 加入到栈中
当前数 $x$ 和栈顶开始往下的任意个数( $\ge 2$ )的数的和相等，那么我们需要将所有这些数都取出来，并把一个新的数 $2*x$ 加入到栈中

由于正整数个数 $n$ 的范围为[1,1000]，因此直接模拟栈实现题目所要求的操作即可。

唯一需要注意的是，在将数字合并之后再次压入栈的同时，可能还会触发数字合并的操作，比如说：

当前栈中有3个数，分别为2，4，3。此时，我们需要将一个数3加入到栈中，我们先是触发了第一个情况，于是我们把3取出，得到了一个新的数 $2*3=6$ ，并准备将6加入到栈中。这时栈里面有2个数分别为2，4，于是我们又触发了第二个条件，取出2和4，并得到了数字12。

最终，栈里面仅有一个数字，也就是12。

在最坏情况下，在每次压入栈时，都会遍历前面所有数字判断是否有数字（或者一串数字的和）与入栈数字相等(比如一个单调递减的序列)，因此该方法的时间复杂度为： $O(N^2)$

代码

C++

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long

const int maxn=1e3+10;
ll stack[maxn];
int top;

int main(){
	ll x;
	while(scanf("%lld",&x)!=EOF){//读入数据 
		while(1){
		// 存在合并后压入栈再次合并的情况，因此循环判断是否有合并的情况 
			bool flag=false;
			ll tmp=0;
			for(int i=top;i&&top;--i){// 暴力查找是否和为x的数 
				tmp+=stack[i];
				if(tmp==x){// 存在一段和为x，合并，并更新栈 
					x=x+tmp;
					top=i-1;
					flag=true;
					break;
				}
			}
			if(flag==false) 
				break;
		}
		stack[++top]=x;
	}
	while(top){
		printf("%lld ",stack[top]);
		top--;
	}
	
	return 0;
}

python

maxn = 1010
stack = [0] * maxn
top = 0

while True:
    x = int(input())  # 读入数据
    if x == -1:
        break
    while True:
        flag = False
        tmp = 0
        for i in range(top, 0, -1):  # 暴力查找是否和为x的数
            tmp += stack[i]
            if tmp == x:  # 存在一段和为x，合并，并更新栈
                x = x + tmp
                top = i - 1
                flag = True
                break
        if not flag:
            break
    top += 1
    stack[top] = x

while top:
    print(stack[top], end=" ")
    top -= 1

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final int maxn = 1010;
        long[] stack = new long[maxn];
        int top = 0;

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLong()) {
            long x = scanner.nextLong(); // 读入数据
            while (true) {
                boolean flag = false;
                long tmp = 0;
                for (int i = top; i > 0; i--) { // 暴力查找是否和为x的数
                    tmp += stack[i];
                    if (tmp == x) { // 存在一段和为x，合并，并更新栈
                        x = x + tmp;
                        top = i - 1;
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    break;
                }
            }
            top++;
            stack[top] = x;
        }
        scanner.close();

        while (top > 0) {
            System.out.print(stack[top] + " ");
            top--;
        }
    }
}

Go

package main

import "fmt"

const maxn = 1010

func main() {
	var stack [maxn]int64 // 栈数组
	top := 0 // 栈顶指针

	var x int64
	for {
		_, err := fmt.Scanf("%d", &x) // 读入数据
		if err != nil {
			break
		}
		for {
			flag := false // 标记是否存在合并的情况
			var tmp int64 // 临时变量存储和
			for i := top; i > 0; i-- { // 暴力查找是否和为x的数
				tmp += stack[i]
				if tmp == x { // 存在一段和为x，合并，并更新栈
					x = x + tmp
					top = i - 1
					flag = true
					break
				}
			}
			if !flag {
				break
			}
		}
		top++
		stack[top] = x
	}

	for top > 0 {
		fmt.Printf("%d ", stack[top])
		top--
	}
}

Js

const maxn = 1010; // 最大数组长度
let stack = new Array(maxn); // 栈数组
let top = 0; // 栈顶指针

function main() {
    let input = require('readline-sync'); // 导入readline-sync模块，用于读取用户输入
    
    while (true) {
        let x = parseInt(input.question()); // 读入数据
        if (isNaN(x)) { // 判断输入是否为数字，若不是则退出循环
            break;
        }
        while (true) {
            let flag = false; // 标记是否存在合并的情况
            let tmp = 0; // 临时变量存储和
            for (let i = top; i > 0; i--) { // 暴力查找是否和为x的数
                tmp += stack[i];
                if (tmp === x) { // 存在一段和为x，合并，并更新栈
                    x = x + tmp;
                    top = i - 1;
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                break;
            }
        }
        top++;
        stack[top] = x;
    }

    while (top > 0) {
        process.stdout.write(stack[top] + " "); // 输出栈顶元素并空格分隔
        top--;
    }
}

main(); // 调用主函数执行

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

# Submissions

316

Accepted

Uploaded By

TaZi

2 solutions

思路：模拟栈

代码

C++

python

Java

Go

Js

Information

Status

Development

Support