题目 https://www.luogu.org/problem/P1631
开一个堆, 先把所有 \(a[i]+b[1]\) 压进优先队列.
然后每次把最小的取出来, 把对应的 \(a[i]\) 的下一个 \(b[j]\) 拿出来加进去.
- #include<bits/stdc++.h>
- using namespace std;
- namespace IO
- {
- char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[15],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
- inline char Get() { return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++); }
- inline void Flush() { fwrite(obuf,1,oS-obuf,stdout),oS=obuf; }
- inline void Put(register char x) { *oS++=x; if(oS==oT) Flush(); }
- inline int read(){register int x=0,f=0;register char ch=Get();while((ch>57||ch<48)&&ch^'-')ch=Get();if(ch=='-')ch=Get(),f=1;while(ch>=48&&ch<=57)x=x*10+(ch^48),ch=Get();return f? -x:x;}
- inline void write(register int x) { register int top=0; if(x<0)Put('-'),x=-x; if(!x) Put('0'); while(x) st[++top]=(x%10)+48,x/=10; while(top) Put(st[top--]); Put(' '); }
- }
- using namespace IO;
- const int N=100007;
- int a[N],b[N],c[N];
- priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>>q;
- int main()
- {
- register int i,n=read();
- for(i=1;i<=n;++i) a[i]=read();
- for(i=1;i<=n;++i) b[i]=read(),c[i]=1,q.push(pair<int,int>(a[1]+b[i],i));
- while(n--) write(q.top().first),i=q.top().second,q.pop(),q.push(pair<int,int>(a[++c[i]]+b[i],i));
- return Flush(),0;
- }
来源: http://www.bubuko.com/infodetail-3200052.html