目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

向一个空栈中依次存入正整数，假设入栈元素 n(1<=n<=2^31-1)按顺序依次为 nx…n4、 n3、n2、 n1, 每当元素入栈时，如果 n1=n2+…+ny(y 的范围[2,x]， 1<=x<=1000)，则 n1~ny 全部元素出栈，重新入栈新元素 m(m=2*n1)。

如：依次向栈存入 6、 1、 2、 3, 当存入 6、 1、 2 时，栈底至栈顶依次为[6、 1、 2]；当存入 3时， 3=2+1， 3、 2、 1 全部出栈，重新入栈元素 6(6=2*3)，此时栈中有元素 6；

因为 6=6，所以两个 6 全部出栈，存入 12，最终栈中只剩一个元素 12。

输入描述

使用单个空格隔开的正整数的字符串，如”5 6 7 8″， 左边的数字先入栈，输入的正整数个数为 x， 1<=x<=1000。

输出描述

最终栈中存留的元素值，元素值使用空格隔开，如”8 7 6 5″， 栈顶数字在左边。 6 1 2 3

用例

题目解析

这题我们先求出，以每个输入元素为结尾子区间的和，存入dp数组中。如下图dp数组所示：

然后从第1个元素开始遍历（索引0开始），对比arr[i]和dp[i-1]，此时

有三种可能：

• arr[i] === dp[i-1]
• arr[i] > dp[i-1]
• arr[i] < dp[i-1]

其中dp[i-1]代表arr数组0~i-1索引元素值的总和。

如果arr[i] > dp[i-1]，说明arr数组0~i-1的元素即使全算上，不够arr[i]打，即无法合并。

如果arr[i] === dp[i-1]，arr[i]可以和前面0~i-1个数组元素合并。此时我们可以将arr[i]更改为dp[i]的值，即2 * dp[i-1] 或者 2 * arr[i]，然后将arr数组的0~i-1索引删除，如下面例子所示

如果arr[i] < dp[i-1]，则说明 arr数组 在 0~i-1 中存在子区间的和  可能 等于 arr[i]。

而这个子区间的右边界又必须为i-1，因此我们只能不断退出0~i-1的头部，第一次退出arr[0]，然后算arr的1~i-1区间和是否等于arr[i]，若不相等，则继续退出头部arr[1]，然后算arr的2~i-1的区间和是否等于arr[i]，若不相等，处理同上

 若相等，则我们需要将arr[i]的值替换为 2~i-1的区间和 * 2，然后删除arr数组的 2~i-1 子序列。

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {const arr = line.split(" ").map(Number);console.log(getRemain(arr));
});function getRemain(arr) {const dp = [arr[0]];for (let i = 1; i < arr.length; i++) {dp[i] = arr[i] + dp[i - 1];}for (let i = 1; i < arr.length; i++) {if (arr[i] === dp[i - 1]) {arr[i] = dp[i];arr.splice(0, i);dp.splice(0, i);i = 0;continue;}if (arr[i] < dp[i - 1]) {let right = i - 1;let left = i - 1;while (left >= 1) {let subSum = dp[right] - dp[left - 1];if (subSum > arr[i]) break;if (subSum === arr[i]) {arr[i] *= 2;arr.splice(left, right - left + 1);dp.splice(left, right - left + 1);i = left;break;}left--;}}}return arr.reverse().join(" ");
}