304392: CF840A. Leha and Function

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Leha and Function

题意翻译

## 题目描述 Leha喜欢各种各样奇怪的事。最近他喜欢上了函数$F(n,k)$ 。考虑所有集合$[1,2,\dots,n]$ 的有$k$ 个元素的子集。为这些子集找到其中最小的元素。$F(n,k)$ — 就是所有$k$ 个元素子集中的最小元素的数学期望。 但是仅仅这个函数还不够使他高兴。他想要在这上面做一些更有趣的事情。他的妈妈给他带来了两个数组$A$ 和$B$ ,每个都有$m$ 个整数。对于所有的$i,j$ ($1\leq i,j\leq m$ )都有$a_i\geq b_j$ 。帮助Leha重新排列$A$ 数组来使得有最大的$\sum_{i=1}^m F(A_i',B_i)$ ,$A'$ 是重排后的数组。 ### 输入格式: 输入数据的第一行包含一个整数$m$ ($1\leq m\leq 2\cdot10^5$ ) — $A$ 数组和$B$ 数组的长度。 下一行包含$m$ 个整数$a_1,a_2,\dots,a_m$ ($1\leq a_i\leq 10^9$ ) — $A$ 数组。 下一行包含$m$ 个整数$b_1,b_2,\dots,b_m$ ($1\leq b_i\leq 10^9$ ) — $B$ 数组。 ### 输出格式: 输出$m$ 个整数$a'_i,a'_2,\dots,a'_m$ — $A'$ 数组,一个$A$ 数组的排列。 翻译贡献者UID:35700

题目描述

Leha like all kinds of strange things. Recently he liked the function $ F(n,k) $ . Consider all possible $ k $ -element subsets of the set $ [1,2,...,n] $ . For subset find minimal element in it. $ F(n,k) $ — mathematical expectation of the minimal element among all $ k $ -element subsets. But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays $ A $ and $ B $ , each consists of $ m $ integers. For all $ i,j $ such that $ 1<=i,j<=m $ the condition $ A_{i}>=B_{j} $ holds. Help Leha rearrange the numbers in the array $ A $ so that the sum ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF840A/0fb9ca71d5a9b45e62436892e025604359337ace.png) is maximally possible, where $ A' $ is already rearranged array.

输入输出格式

输入格式


First line of input data contains single integer $ m $ ( $ 1<=m<=2·10^{5} $ ) — length of arrays $ A $ and $ B $ . Next line contains $ m $ integers $ a_{1},a_{2},...,a_{m} $ ( $ 1<=a_{i}<=10^{9} $ ) — array $ A $ . Next line contains $ m $ integers $ b_{1},b_{2},...,b_{m} $ ( $ 1<=b_{i}<=10^{9} $ ) — array $ B $ .

输出格式


Output $ m $ integers $ a'_{1},a'_{2},...,a'_{m} $ — array $ A' $ which is permutation of the array $ A $ .

输入输出样例

输入样例 #1

5
7 3 5 3 4
2 1 3 2 3

输出样例 #1

4 7 3 5 3

输入样例 #2

7
4 6 5 8 8 2 6
2 1 2 2 1 1 2

输出样例 #2

2 6 4 5 8 8 6

Input

题意翻译

## 题目描述 Leha喜欢各种各样奇怪的事。最近他喜欢上了函数$F(n,k)$ 。考虑所有集合$[1,2,\dots,n]$ 的有$k$ 个元素的子集。为这些子集找到其中最小的元素。$F(n,k)$ — 就是所有$k$ 个元素子集中的最小元素的数学期望。 但是仅仅这个函数还不够使他高兴。他想要在这上面做一些更有趣的事情。他的妈妈给他带来了两个数组$A$ 和$B$ ,每个都有$m$ 个整数。对于所有的$i,j$ ($1\leq i,j\leq m$ )都有$a_i\geq b_j$ 。帮助Leha重新排列$A$ 数组来使得有最大的$\sum_{i=1}^m F(A_i',B_i)$ ,$A'$ 是重排后的数组。 ### 输入格式: 输入数据的第一行包含一个整数$m$ ($1\leq m\leq 2\cdot10^5$ ) — $A$ 数组和$B$ 数组的长度。 下一行包含$m$ 个整数$a_1,a_2,\dots,a_m$ ($1\leq a_i\leq 10^9$ ) — $A$ 数组。 下一行包含$m$ 个整数$b_1,b_2,\dots,b_m$ ($1\leq b_i\leq 10^9$ ) — $B$ 数组。 ### 输出格式: 输出$m$ 个整数$a'_i,a'_2,\dots,a'_m$ — $A'$ 数组,一个$A$ 数组的排列。 翻译贡献者UID:35700

加入题单

上一题 下一题 算法标签: