序列合并
发布时间:2020-12-14 04:42:52 所属栏目:大数据 来源:网络整理
导读:题目描述 有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到 N^2 个和,求这 N^2 个和中最小的N个。 输入输出格式 输入格式: 第一行一个正整数N; 第二行N个整数 A_i, ?满足 A i ? ≤ A i + 1 ?且 A i ? ≤ 10^9 ; 第三行N个整数 B_i ,满足 B i
题目描述有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到N^2个和,求这N^2个和中最小的N个。 输入输出格式输入格式: 第一行一个正整数N; 第二行N个整数A_i,?满足Ai?≤Ai+1?且Ai?≤10^9; 第三行N个整数B_i,满足Bi?≤Bi+1?且Bi?≤10^9. 【数据规模】 对于50%的数据中,满足1<=N<=1000; 对于100%的数据中,满足1<=N<=100000。 ? 输出格式: 输出仅一行,包含N个整数,从小到大输出这N个最小的和,相邻数字之间用空格隔开。 ? 输入输出样例
输入样例#1:?
3 2 6 6 1 4 8
输出样例#1:?
3 6 7 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<queue> 5 #include<cmath> 6 using namespace std; 7 const int M=100005; 8 int n; 9 int a[M],b[M],t[M]; 10 struct node{ 11 int x,y,sum; 12 }; 13 bool operator >(const node &a,const node &b){ 14 return a.sum>b.sum; 15 } 16 priority_queue<node,vector<node>,greater<node> >q; 17 inline int get(){ 18 char c=getchar(); 19 while (c>‘9‘||c<‘0‘) c=getchar(); 20 int res=0; 21 while (c>=‘0‘&&c<=‘9‘) { 22 res=(res<<3)+(res<<1)+c-‘0‘; 23 c=getchar(); 24 } 25 return res; 26 } 27 bool cmp(int a,int b){ 28 return a<b; 29 } 30 int main(){ 31 n=get(); 32 for (int i=1;i<=n;i++) a[i]=get(),t[i]=1; 33 for (int i=1;i<=n;i++) b[i]=get(); 34 sort(b+1,b+n+1,cmp); 35 int cnt=0; 36 for (int i=1;i<=n;i++) q.push((node){i,t[i],a[i]+b[t[i]]}); 37 while (cnt!=n){ 38 printf ("%d ",q.top().sum); 39 int cmp=q.top().x; 40 t[cmp]++; 41 q.pop(); 42 q.push((node){cmp,t[cmp],a[cmp]+b[t[cmp]]}); 43 cnt++; 44 } 45 return 0; 46 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |