写在前面

本次给大家带来2026年8月7日联想笔试题的1道题，本场机考题目可在咱们平台上在线刷题。

第一题：把每次合并看成把原数组划分为若干连续段，目标转化为让各段的段和非递减并最大化段数，可用前缀和配合动态规划求最大合法段数，最终答案为 。

塔子哥的配套刷题网站:codefun2000.com

第1题-邻项合并归序

题目内容

产线质检得到一条长度为  的整型读数序列 。允许反复选取一对相邻读数，将其合并为一个新读数，新读数的值为两者之和。

需要使整条序列从左至右保持非降：任意相邻两项中，左侧读数的数值不超过右侧读数。

请计算达成上述目标所需的最少合并次数。

输入描述

首先一行一个正整数 （表示随后有多少条记录）。

对于每条记录：

第一行一个正整数 ，表示该条记录中读数的个数。

第二行  个正整数 ，表示读数序列。，，

输出描述

按记录顺序，对每条记录各写出一行一个非负整数，表示该条记录对应的最少合并次数。

样例1

输入

332 1 341 2 3 435 1 6

输出

101

说明

第一条记录：将  与  合并，得到 ，已满足 ，共合并  次。

第二条记录：序列  本身已单调不减，无需合并。

第三条记录：将  与  合并，得到 ，共合并  次。

样例2

输入

153 2 1 4 5

输出

1

说明

将中间的  与  合并，得到 ，相邻读数依次为 ，共合并  次。

题解

解题思路

本题考查贪心与从右向左维护后缀信息，将「最少合并次数」转化为一次线性扫描。

1. 合并只会减少数组长度，且合并后的新元素一定比被合并的右侧元素更大。因此从右向左处理时，只需关心当前位置右侧已经整理好的「代表值」。
2. 设从右向左扫描时，右侧已整理块的代表值为 （初始为极大值）。若当前 ，说明  可以直接接在右侧块前面，令 。
3. 若 ，则  与右侧相邻元素必然违反非降，必须把  合并进右侧块，合并次数 ，且合并后右侧块的代表值变为 （用  位整型存储）。
4. 每个位置最多触发一次合并，答案即为扫描过程中合并次数之和。多组询问按题面格式逐组计算即可。

常见假解：

• 从左向右遇到逆序就立刻合并：例如  会多合并，正解为  次而非  次；
• 用  位整数累加合并后的和，在  接近 、多次合并时溢出；
• 误以为答案与元素个数  无关而漏读多组询问。

复杂度分析

• 时间复杂度：每组 ，共 ，在 、 下足够。
• 空间复杂度： 读入数组，或  额外空间（若边读边处理）。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

defmin_merges(v: list[int]) -> int:# 从右向左贪心：维护右侧块的代表值 suf，当前项过大则必须合并  suf = 10**18  ans = 0for x in reversed(v):if x <= suf:      suf = xelse:      ans += 1      suf += xreturn ansdefmain() -> None:  q = int(input())for _ in range(q):    n = int(input())    v = list(map(int, input().split()))    print(min_merges(v))if __name__ == "__main__":  main()