P1631

原题链接 方法1： 有点像剪枝。 \(i\)从\(1~n\)循环，\(j\)同理，如果\(a[i]+b[j]\)放不进去，那么\(a[i]+b[j+1]\)也放不进去 code #include<bits/stdc++.h> using namespace std; int a[100005]; i ......

P1631 序列合并 思路 思路一 题目要求的是二维的，太麻烦，所以我们可以将其用一维划分，将每一组都变成线性的，那线性的就很好求了，直接排序然后从前往后算即可，那么就可以将这 \(n\) 组合并，但如果是整个都算出来再合并就会是 \(O(n^2)\) 的，所以可以只记录当前的，那么对于当前的最小的 ......

P1631 序列合并 这个没做出来属实有些惭愧。看了题解觉得很妙。如果直接想的话可能反而很麻烦 题目是给两个n个数的不下降序列，问这两个序列任意各取出一个后相加的最小的n个数是什么。 直接贴题解吧题解 P1631 【序列合并】 一共会产生n*n个数， a[1]+b[1]<=a[1]+b[2].... ......

主要思路：由于题干中说明给出的两个序列是单调不降的，所以不需要再对序列进行一个排序。这里其实有一点贪心的意思但不完全是贪心算法。首先把两个序列分别放入两个数组，然后进行各个元素和的遍历。构建一个优先序列pq，优先序列会对里面的元素自动降序排列，每次遍历都判断和是否小于pq 内的最大元素，即pq.to ......