#Algo0107. Minimum Array

    ID: 71 Type: RemoteJudge 2000ms 256MiB Tried: 49 Accepted: 23 Difficulty: 4 Uploaded By: Tags>算法基础二分贪心数据结构平衡树线段树cf*1700

Minimum Array

题目描述

给你两个数组 aabb, 长度都是 nn. 两个数组的所有元素都在 00n1n-1 之间。

你可以重新排列数组 bb 中的元素(如果你想的话,你也可以让数组保持它原来的样子)。随后,定义长度也为 nn 的数组 cc , 它的第 ii 个元素满足 ci=(ai+bi)%nc_i = (a_i + b_i) \% n

你需要重新排列数组 bb 来得到字典序尽可能小的数组cc。当存在 ii (1in1 \le i \le n) 使得xi<yix_i < y_i, 同时对任意的 jj (1j<i1 \le j < i) 有 xj=yjx_j = y_j 时,我们称长度为 nn 的数组 xx 字典序小于长度为 nn 的数组 yy

输入

第一行输入一个整数 nn (1n21051 \le n \le 2 \cdot 10^5) 表示 aa, bbcc 中的元素个数。

第二行有 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n (0ai<n0 \le a_i < n), 其中 aia_iaa 的第 ii 个元素。

第三行有 nn 个整数 b1,b2,,bnb_1, b_2, \dots, b_n (0bi<n0 \le b_i < n), 其中 bib_ibb 的第 ii 个元素。

输出

输出字典序尽可能小的数组 cc. 注意你需要做的是去将数组 bb 中的元素重新排列,然后才得到字典序尽可能小的数组 cc . 其中 ci=(ai+bi)%nc_i = (a_i + b_i) \% n.

4
0 1 2 1
3 2 1 1
1 0 0 2
7
2 5 1 5 3 4 3
2 4 3 5 6 5 1
0 0 0 1 0 2 4