題目描述

有兩個(gè)長(zhǎng)度都是N的序列A和B，在A和B中各取一個(gè)數(shù)相加可以得到N^2N2個(gè)和，求這N^2N2個(gè)和中最小的N個(gè)。

輸入輸出格式

輸入格式：

?

第一行一個(gè)正整數(shù)N；

第二行N個(gè)整數(shù)A_iAi?, 滿足A_i\le A_{i+1}Ai?≤Ai+1?且A_i\le 10^9Ai?≤109;

第三行N個(gè)整數(shù)B_iBi?, 滿足B_i\le B_{i+1}Bi?≤Bi+1?且B_i\le 10^9Bi?≤109.

【數(shù)據(jù)規(guī)模】

對(duì)于50%的數(shù)據(jù)中，滿足1<=N<=1000；

對(duì)于100%的數(shù)據(jù)中，滿足1<=N<=100000。

?

輸出格式：

?

輸出僅一行，包含N個(gè)整數(shù)，從小到大輸出這N個(gè)最小的和，相鄰數(shù)字之間用空格隔開。

?

輸入輸出樣例

輸入樣例#1：
3 2 6 6 1 4 8 輸出樣例#1：
3 6 7

?

題解

• 其實(shí)就是每次找最小的兩個(gè)，但是題目是每個(gè)數(shù)可以用多次，如何不重復(fù)的去做才是終點(diǎn)
• 首先，對(duì)于A序列的第一個(gè)數(shù)一定是要選的，那么就可以先把B數(shù)列中所有數(shù)與它的和加入優(yōu)先隊(duì)列中，并記錄下當(dāng)前與A序列第一個(gè)數(shù)相加，可以用P數(shù)組存
• 那么每次就輸出隊(duì)首，這個(gè)沒(méi)問(wèn)題吧
• 然后將對(duì)首的A數(shù)列變后一個(gè)，將之前記錄P數(shù)組+1，再加上自己，再加入隊(duì)列里

代碼

1 #include <cstdio> 2 #include <queue> 3 #include <vector> 4 #define N 100010 5 using namespace std; 6 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q; 7 int n,k,a[N],b[N],p[N]; 8 int main() 9 { 10 scanf("%d",&n); 11 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 12 for (int i=1;i<=n;i++) scanf("%d",&b[i]),p[i]=1,Q.push(make_pair(a[1]+b[i],i)); 13 while (n--) printf("%d ",Q.top().first),k=Q.top().second,Q.pop(),Q.push(make_pair(a[++p[k]]+b[k],k)); 14 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Comfortable/p/10327991.html

總結(jié)

以上是生活随笔為你收集整理的[优先队列] 洛谷 P1631 序列合并的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。