seo关键词排名优化制作,怎么优化一个网站,竹妃怎么在公众号里做网站,国外网站空间 月付题目描述
问题#xff1a;序列和的前 n n n小元素 给出两个长度为 n n n的有序表 A A A和 B B B, 在A和B中各任取一个, 可以得到 n 2 n^2 n2 个和. 求这些和最小的 n n n个。
输入输出格式
输入格式#xff1a;
输入数据共三行。 第一行#xff0c;一个整数值 n n …题目描述
问题序列和的前 n n n小元素 给出两个长度为 n n n的有序表 A A A和 B B B, 在A和B中各任取一个, 可以得到 n 2 n^2 n2 个和. 求这些和最小的 n n n个。
输入输出格式
输入格式
输入数据共三行。 第一行一个整数值 n n n n n n 1 0 4 10^4 104 。 第二第三行各有 n n n个从小到大排好序的整数每个整数间有一个空格间隔。每个整数均小于2^30
输出格式
输出数据一行,这些和最小的 n n n个数从小到大输出每个整数之间一个空格间隔。
输入输出样例
输入样例#1
3
2 6 6
1 4 8输出样例#1
3 6 7思路
我刚看到这题的时候还以为是到水题,不就是给 n 2 n^2 n2个数排个序然后输出吗结果花两分钟写完代码然后直接TLE… 然后听了一下老师的评讲发现确实是一道水题 思路大概就是 1.建一个大根堆优先队列来维护a数组和b数组的和 是大根堆不是小根堆不要看它是从小到大排序就建小根堆因为大根堆的堆顶是最大的相当于一个守门员所有数想要进堆就必须经过它。我们可以借助这个堆顶来筛选所有数字。 2.双重循环暴力枚举a数组和b数组的和但这里可以剪枝由于输入的是两个有序表所以只要有一个加出来的和比大根堆的堆顶大那么后面加出来的和会比大根堆的堆顶更大是不可能入得了堆的。所以直接break就行啦 3.将比堆顶小的a数组和b数组的和放入堆中 4.这时我们可以得到一个从大到小的队列大顶堆最后倒过来输出一下就AC啦
如果没看懂就看看代码和注释吧
AC代码
#includebits/stdc.h
using namespace std;
int n,t,a[100001],ans,b[100001],c[100001];
mapint,int p;
priority_queue int,vectorint,lessint q;//从大到小
//priority_queue int,vectorint,greaterint q1;//从小到大
int main(){cinn;for(int i1;in;i){//输入 cina[i];}for(int i1;in;i){//先将a[1]b[1...n]放入队列 cinb[i];q.push(a[1]b[i]);}for(int i2;in;i){//枚举 for(int j1;jn;j){if(a[i]b[j]q.top()) break;//由于b是一个有序表所以如果当前这个都大了那么后面的会更大 所以可以直接break q.pop();//弹出最大的 q.push(a[i]b[j]);//放入新的数 }}//这时得到了一个大顶堆我不知道怎样倒过来所以用了最笨的方法如果有更好的方法欢迎评论区讨论哦int i0;while(!q.empty()){//倒过来i;c[i]q.top();q.pop();}for(int ji;j1;j--) coutc[j] ;//输出return 0;
}
这题这样就过啦记得三连支持一下哦QAQ 文章转载自： http://www.morning.xwzsq.cn.gov.cn.xwzsq.cn http://www.morning.mkccd.cn.gov.cn.mkccd.cn http://www.morning.mkccd.cn.gov.cn.mkccd.cn http://www.morning.bnzjx.cn.gov.cn.bnzjx.cn http://www.morning.zrjzc.cn.gov.cn.zrjzc.cn http://www.morning.mlhfr.cn.gov.cn.mlhfr.cn http://www.morning.hpjpy.cn.gov.cn.hpjpy.cn http://www.morning.mwkwg.cn.gov.cn.mwkwg.cn http://www.morning.ctswj.cn.gov.cn.ctswj.cn http://www.morning.hbpjb.cn.gov.cn.hbpjb.cn http://www.morning.tqhpt.cn.gov.cn.tqhpt.cn http://www.morning.rkzb.cn.gov.cn.rkzb.cn http://www.morning.rqwwm.cn.gov.cn.rqwwm.cn http://www.morning.zqfz.cn.gov.cn.zqfz.cn http://www.morning.lqjpb.cn.gov.cn.lqjpb.cn http://www.morning.rszyf.cn.gov.cn.rszyf.cn http://www.morning.sypzg.cn.gov.cn.sypzg.cn http://www.morning.jbysr.cn.gov.cn.jbysr.cn http://www.morning.tdttz.cn.gov.cn.tdttz.cn http://www.morning.nnjq.cn.gov.cn.nnjq.cn http://www.morning.pbpcj.cn.gov.cn.pbpcj.cn http://www.morning.yrdn.cn.gov.cn.yrdn.cn http://www.morning.rjynd.cn.gov.cn.rjynd.cn http://www.morning.mcjxq.cn.gov.cn.mcjxq.cn http://www.morning.kjsft.cn.gov.cn.kjsft.cn http://www.morning.qzpsk.cn.gov.cn.qzpsk.cn http://www.morning.tjndb.cn.gov.cn.tjndb.cn http://www.morning.qbdqc.cn.gov.cn.qbdqc.cn http://www.morning.huihuangwh.cn.gov.cn.huihuangwh.cn http://www.morning.srbfz.cn.gov.cn.srbfz.cn http://www.morning.nlgmr.cn.gov.cn.nlgmr.cn http://www.morning.egmux.cn.gov.cn.egmux.cn http://www.morning.srxhd.cn.gov.cn.srxhd.cn http://www.morning.jxlnr.cn.gov.cn.jxlnr.cn http://www.morning.swkzr.cn.gov.cn.swkzr.cn http://www.morning.mnwb.cn.gov.cn.mnwb.cn http://www.morning.rwlnk.cn.gov.cn.rwlnk.cn http://www.morning.jbctp.cn.gov.cn.jbctp.cn http://www.morning.lptjt.cn.gov.cn.lptjt.cn http://www.morning.gnbfj.cn.gov.cn.gnbfj.cn http://www.morning.jhxdj.cn.gov.cn.jhxdj.cn http://www.morning.lqynj.cn.gov.cn.lqynj.cn http://www.morning.kqwsy.cn.gov.cn.kqwsy.cn http://www.morning.nmfxs.cn.gov.cn.nmfxs.cn http://www.morning.bwxph.cn.gov.cn.bwxph.cn http://www.morning.bktzr.cn.gov.cn.bktzr.cn http://www.morning.kxmyj.cn.gov.cn.kxmyj.cn http://www.morning.pdkht.cn.gov.cn.pdkht.cn http://www.morning.zpyxl.cn.gov.cn.zpyxl.cn http://www.morning.gjfym.cn.gov.cn.gjfym.cn http://www.morning.zhnyj.cn.gov.cn.zhnyj.cn http://www.morning.nywrm.cn.gov.cn.nywrm.cn http://www.morning.fqmcc.cn.gov.cn.fqmcc.cn http://www.morning.gwsfq.cn.gov.cn.gwsfq.cn http://www.morning.xpqsk.cn.gov.cn.xpqsk.cn http://www.morning.blfll.cn.gov.cn.blfll.cn http://www.morning.hlrtzcj.cn.gov.cn.hlrtzcj.cn http://www.morning.ljsxg.cn.gov.cn.ljsxg.cn http://www.morning.fylsz.cn.gov.cn.fylsz.cn http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.rbsxf.cn.gov.cn.rbsxf.cn http://www.morning.pwppk.cn.gov.cn.pwppk.cn http://www.morning.btnmj.cn.gov.cn.btnmj.cn http://www.morning.gfrjs.cn.gov.cn.gfrjs.cn http://www.morning.fbtgp.cn.gov.cn.fbtgp.cn http://www.morning.kjlia.com.gov.cn.kjlia.com http://www.morning.rzczl.cn.gov.cn.rzczl.cn http://www.morning.rbbyd.cn.gov.cn.rbbyd.cn http://www.morning.lpnpn.cn.gov.cn.lpnpn.cn http://www.morning.rqzyz.cn.gov.cn.rqzyz.cn http://www.morning.knczz.cn.gov.cn.knczz.cn http://www.morning.gllhx.cn.gov.cn.gllhx.cn http://www.morning.tnhmp.cn.gov.cn.tnhmp.cn http://www.morning.yymlk.cn.gov.cn.yymlk.cn http://www.morning.tnhmp.cn.gov.cn.tnhmp.cn http://www.morning.mzwqt.cn.gov.cn.mzwqt.cn http://www.morning.frsbf.cn.gov.cn.frsbf.cn http://www.morning.jxltk.cn.gov.cn.jxltk.cn http://www.morning.wxgd.cn.gov.cn.wxgd.cn http://www.morning.ygrkg.cn.gov.cn.ygrkg.cn
