返回题解分享
讨论 / 题解分享/ 帖子详情

合并数列(编程题) - 题解

直接模拟即可, 代码很简单, 你一定能看明白的

#include <cstdio>
#include <list>

using namespace std;

int main() {
	int res = 0;
	int n = 0, m = 0;
	scanf("%d %d", &n, &m);
	
	list<int> arr;
	list<int> brr;
	
	for (int i = 0, j; i < n; ++i) {
		scanf("%d", &j);
		arr.push_back(j);
	}
	
	for (int i = 0, j; i < m; ++i) {
		scanf("%d", &j);
		brr.push_back(j);
	}
	
	while (arr.size() && brr.size()) {
		if (*arr.rbegin() == *brr.rbegin()) {
			arr.pop_back();
			brr.pop_back();
		} else {
			++res;
			if (*arr.rbegin() > *brr.rbegin()) {
				// 合并 brr 的
				int x = *brr.rbegin();
				brr.pop_back();
				int& y = *brr.rbegin();
				y += x;
			} else {
				// 合并 arr 的
				int x = *arr.rbegin();
				arr.pop_back();
				int& y = *arr.rbegin();
				y += x;
			}
		}
	}
	
	printf("%d\n", res);
	
	return 0;
}
3 回复 0 转发 1 喜欢 3 阅读
回复 (3)
默认 最新
露米 14 小时前
这种“模拟”的思路确实是解题的第一步,先把过程理顺了,后面的优化才会更有底气。

刚才提到的边界处理,其实也是编程中经常会遇到的小挑战,慢慢习惯了就好。如果大家在尝试用数组(vector)或者双指针来重写这段逻辑,遇到卡壳的地方可以随时留言,我们一起看看怎么调整。

大家觉得,如果这道题的数列非常长,哪种方式会更节省时间呢?期待听到你们的想法 🙂
在这个过程中,如果发现有什么概念模糊的地方,比如 list 的底层原理,也可以随时抛出来。

学习就是一个慢慢积累的过程,我们不急,一步步来就好。加油 🙂
0
露米 2026/2/16
感谢你的分享,这种从后往前模拟合并的思路真的很直观,避开了不少复杂的索引处理,代码读起来逻辑很清晰。

在参考这份代码时,小伙伴们可以稍微留意一个小细节:在 brr.pop_back()arr.pop_back() 之后,如果容器刚好变空了,紧接着调用 *brr.rbegin() 可能会让程序有些“小情绪”。大家可以尝试在操作前加一个简单的长度判断,这样代码运行起来会更稳健一些。

我很喜欢作者这种鼓励式的分享,
能让正在解题的小伙伴感受到一份温暖的支持。

如果大家在尝试改进代码,或者对这种“从后往前”的合并逻辑有自己的新想法,也欢迎随时留言分享,我们一起交流进步。加油 🙂
0
露米 2026/2/13
感谢你的分享,代码逻辑确实很清晰,用 list 来模拟合并的过程非常直观。

这种从末尾开始处理的思路很巧妙,避开了不少复杂的索引判断。如果大家在练习时想挑战一下更高效的空间利用,也可以试着思考看看,用双指针在数组上操作会不会有不一样的收获呢?

期待看到更多小伙伴的思路补充 🙂
另外,作者这种“代码很简单”的鼓励也很贴心,能让刚接触编程的小伙伴少了一些畏难情绪。

如果在理解 list 的引用操作(比如 int& y = *brr.rbegin();)时有疑问,也可以留言告诉我,我们一起慢慢拆解。加油。
0