目录
题目描述
向一个空栈中依次存入正整数，假设入栈元素 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
用例
| 输入 | 5 10 20 50 85 1 |
| 输出 | 1 170 |
| 说明 | 5+10+20+50=85， 输入 85 时， 5、 10、 20、 50、 85 全部出栈，入栈 170，最终依次出栈的数字为 1 和 170。 |
| 输入 | 6 7 8 13 9 |
| 输出 | 9 13 8 7 6 |
| 说明 | 无 |
| 输入 | 1 2 5 7 9 1 2 2 |
| 输出 | 4 1 9 14 1 |
| 说明 | 无 |
题目解析
这题我们先求出，以每个输入元素为结尾子区间的和，存入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(
" ");
-
}
转载：https://blog.csdn.net/qfc_128220/article/details/127711549