手表网站,wordpress 判断移动端,WordPress创建的网站,wordpress wpenqueuescripts序列合并
题目入口
题目描述
有两个长度为 N N N 的单调不降序列 A , B A,B A,B#xff0c;在 A , B A,B A,B 中各取一个数相加可以得到 N 2 N^2 N2 个和#xff0c;求这 N 2 N^2 N2 个和中最小的 N N N 个。
输入格式
第一行一个正整数 N N N#xff1b;
第二…
序列合并
题目入口
题目描述
有两个长度为 N N N 的单调不降序列 A , B A,B A,B在 A , B A,B A,B 中各取一个数相加可以得到 N 2 N^2 N2 个和求这 N 2 N^2 N2 个和中最小的 N N N 个。
输入格式
第一行一个正整数 N N N
第二行 N N N 个整数 A 1 … N A_{1\dots N} A1…N。
第三行 N N N 个整数 B 1 … N B_{1\dots N} B1…N。
输出格式
一行 N N N 个整数从小到大表示这 N N N 个最小的和。
样例 #1
样例输入 #1
3
2 6 6
1 4 8样例输出 #1
3 6 7提示
对于 50 % 50\% 50% 的数据 N ≤ 1 0 3 N \le 10^3 N≤103。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 1≤N≤105 1 ≤ a i , b i ≤ 1 0 9 1 \le a_i,b_i \le 10^9 1≤ai,bi≤109。
题解
设行为 A i A_i Ai 列为 B j B_j Bj 由题知很显然排完序的A数组与B数组的和呈此关系那也知道 A 1 B 1 A_1B_1 A1B1的值是最小的其余关系如图。 证明 a i a i 1 , a_ia_{i1}, aiai1,在 b j b_j bj一定时 a i b j a i 1 b j a_ib_ja_{i1}b_j aibjai1bj b i b i 1 , b_ib_{i1}, bibi1,在 a j a_j aj一定时 b i a j b i 1 a j b_ia_jb_{i1}a_j biajbi1aj 所以左上角最小右下角最大 那我们可以先把 a i b 1 a_ib_1 aib1加入到优先队列中然后弹出最小的假设这个最小值是由 a x b y a_xb_y axby构成那么再把 a x b y 1 a_xb_{y1} axby1放入优先队列中 最后记得重载运算符
Code
#include bits/stdc.husing namespace std;const int Maxn 1e5 10;
int pos_b[Maxn];
int a[Maxn], b[Maxn];
int id[Maxn];
struct node
{int pos;int num;bool operator(const node cur) const{return num cur.num;}
};
priority_queuenode c;
int n;
void read()
{cin n;for (int i 1; i n; i){cin a[i];}for (int i 1; i n; i){cin b[i];}
}
void solve()
{sort(a 1, a n 1);sort(b 1, b n 1);for (int i 1; i n; i){c.push({i, a[i] b[1]});id[i] 1;}for (int i 1; i n; i){node x c.top();c.pop();cout x.num ;int id2 x.pos;c.push({id2, a[id2] b[id[id2]]});}
}
int main()
{read();solve();return 0;
}
