CodeVS/1245

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
最小的N个和	★☆☆☆☆	答案正确	100	2015-7-19 17:40:11	无

代码

1245.cpp代码已折叠 展开折叠内容

显示/移除行号 #include<cstdio> #include<algorithm> #include<iostream> #include<set> using namespace std; typedef pair<int,int> v2; typedef pair<int,v2> v3; #define r1 first #define r2 second.first #define r3 second.second #define m3(u1,u2,u3) make_pair(u1,make_pair(u2,u3)) set<v3> h; /* 之所以用了set而不是priority_queue的原因是……判重 （似乎从第一列开始，逐渐向右也可以解决判重问题） */ int n; int a[100100],b[100100]; int main(){ cin>>n; for(int i=1;i<=n;++i)cin>>a[i]; for(int i=1;i<=n;++i)cin>>b[i]; sort(a+1,a+n+1); sort(b+1,b+n+1); /* a,b从大到小排序 我们可以设二维表A[i][j]=a[i]+b[j] A是有单调性的，每个元素比上，左小 堆中放入最小的A左上角两个节点，可以依次向右、下扩展 */ h.insert(m3(a[1]+b[1],1,1)); for(int i=1;i<=n;++i) { v3 u=*h.begin(),n1=u,n2=u; h.erase(h.begin()); cout<<u.r1<<" "; //每次输出一个最小点，然后把其右边，下面节点放入// ++n1.r2; n1.r1=a[n1.r2]+b[n1.r3]; if(n1.r2<=n)h.insert(n1); ++n2.r3; n2.r1=a[n2.r2]+b[n2.r3]; if(n2.r3<=n)h.insert(n2); }   }