【题解】 洛谷 P1631 序列合并

本文主要是介绍【题解】 洛谷 P1631 序列合并，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这个题提供给了我们一个比较新颖的思考方向：

发现由所有的和可以组成这样的 \(n\) 个偏序集：

然后我们可以考虑把每个偏序集中最小的元素加入一个优先队列中，也就是 \(a_1+b_1,a_2+b_1\dots a_n+b_1\)，然后每取出一个 \(a_i+b_j\)，就将该偏序集中次小的那个元素（即\(a_i+b_{i+1}\)）加入优先队列中（前提是 \(i<n\)），这样求满 \(n\) 个，即为前 \(n\) 小。

正确性证明：

加入偏序集元素的顺序使得我们能保证当前加入的元素是该偏序集中最小的，而优先队列又能保证每次取出的元素是 \(n\) 个偏序集中未取的最小的元素中最小的，所以正确性得证。

#include<bits/stdc++.h>
#define ll long long
//#define int long long
#define lc(k) k<<1
#define rc(k) k<<1|1
const int MAX=1e5+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
	int res = 0, f = 0;
	char ch = readchar();
	for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
	for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
	return f ? -res : res;
}
inline void write(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int a[MAX],b[MAX];
struct node
{
	int id1,id2,w;
	friend bool operator < (node x,node y)
	{
		return x.w>y.w;
	}
};
priority_queue<node> q;
signed main()
{
	int n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	for(int i=1;i<=n;i++) q.push((node){i,1,a[i]+b[1]});
	for(int i=1;i<=n;i++)
	{
		node ff=q.top();q.pop();
		if(ff.id2<n) q.push((node){ff.id1,ff.id2+1,a[ff.id1]+b[ff.id2+1]});
		write(ff.w);
		putchar('\n');
	}
	return 0;
}

这篇关于【题解】 洛谷 P1631 序列合并的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！