cf Educational Codeforces Round 134 C. Min-Max Array Transformation_红鲤鱼遇绿鲤鱼

大大的周 02-07 7640

You are given an array a1,a2,…,an, which is sorted in non-descending order. You decided to perform the following steps to create array b1,b2,…,bn

Create an array d consisting of n arbitrary non-negative integers.Set bi=ai+di for each bi.Sort the array b in non-descending order.

You are given the resulting array b. For each index i, calculate what is the minimum and maximum possible value of di you can choose in order to get the given array b.

Note that the minimum (maximum) di-s are independent of each other, i. e. they can be obtained from different possible arrays d.

Input

The first line contains the single integer t ( 1 ≤ t ≤ 1 0 4 ) (1≤t≤10^4) (1≤t≤104) — the number of test cases.

The first line of each test case contains a single integer n ( 1 ≤ n ≤ 2 ? 1 0 5 ) (1≤n≤2?10^5) (1≤n≤2?105) — the length of arrays a, b and d.

The second line contains n integers a1,a2,…,an ( 1 ≤ a i ≤ 1 0 9 ; a i ≤ a i + 1 ) (1≤a_i≤10^9; a_i≤a_{i+1}) (1≤ai?≤109;ai?≤ai+1?) — the array a in non-descending order.

The third line contains n integers b1,b2,…,bn KaTeX parse error: Expected '}', got 'EOF' at end of input: …^9; bi≤b_{i+1|) — the array b in non-descending order.

Additional constraints on the input: there is at least one way to obtain the array b from the a by choosing an array d consisting of non-negative integers; the sum of n doesn’t exceed 2?10^5 .

Output

For each test case, print two lines. In the first line, print n integers d 1 m i n , d 2 m i n , … , d n m i n d^{min}_1,d^{min}_2,…,d^{min}_n d1min?,d2min?,…,dnmin?, where d i m i n d^{min}_i dimin? is the minimum possible value you can add to ai.

Secondly, print n integers d 1 m a x , d 2 m a x , . . , d n m a x d^{max}_1,d^{max}_2,.., d^{max}_n d1max?,d2max?,..,dnmax?, where d i m a x d^{max}_i dimax? is the maximum possible value you can add to ai.

All dmini and d i m a x d^{max}_i dimax? values are independent of each other. In other words, for each i, d i m i n d^{min}_i dimin? is just the minimum value among all possible values of di. Example Input

4 3 2 3 5 7 11 13 1 1000 5000 4 1 2 3 4 1 2 3 4 4 10 20 30 40 22 33 33 55

Output

5 4 2 11 10 8 4000 4000 0 0 0 0 0 0 0 0 12 2 3 15 23 13 3 15

Note

In the first test case, in order to get d 1 m i n d^{min}_1 d1min?=5 , we can choose, for example, d=[5,10,6]. Then b = [2+5,3+10,5+6] = [7,13,11] = [7,11,13].

For d 2 m i n d^{min}_2 d2min?=4, we can choose d = [9,4,8]. Then b = [2+9,3+4,5+8] = [11,7,13] = [7,11,13].

中文：给你两个非递减的序列 a i a_i ai?和 b i b_i bi?，让你创建一个非负序列 d i d_i di?，使得满足 b i = a i + d i b_i = a_i + d_i bi?=ai?+di?，输出每个满足条件 d i d_i di?的最大值和最小值。

代码：

#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 1; int t, n; int a[maxn], b[maxn]; int mark[maxn]; vector<int> max_ans; int first_bigger_equal(int val) { int lef = 0, rig = n - 1; int mid; while(lef <= rig) { mid = (rig + lef) / 2; if (b[mid] < val) { lef = mid + 1; } else { rig = mid - 1; } } return lef; } int main() { ios::sync_with_stdio(false); cin >> t; while (t--) { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { cin >> b[i]; } max_ans.clear(); for (int i = 0; i < n; i++) { int idx = first_bigger_equal(a[i]); // find first bigger equal a[i] in b int val = b[idx]; if (i != n - 1) { cout << val - a[i] << " "; } else { cout << val - a[i] << endl; } mark[i] = n - idx; } int max_val = b[n-1]; int cnt = 1; for (int i = n - 1; i >= 0; i--, cnt++) { max_ans.push_back(max_val - a[i]); if (cnt == mark[i]) { if (i != 0) { max_val = b[i - 1]; } } } reverse(max_ans.begin(), max_ans.end()); for (int i = 0; i < max_ans.size(); i++) { if (i == max_ans.size() - 1) { cout << max_ans[i] << endl; } else { cout << max_ans[i] << " "; } } } return 0; }

思路：以第一个样例为例，a= [2, 3, 5], b= [7, 11, 13] , d1 最小可以设定为7 - 2 = 5, d1最大可以设定为13 - 2 = 11.同理，d2最小可以设定为7 - 3= 4，最大为11 - 3 = 8。d3 最小为7 - 5 = 2, 最大为13 - 5 = 8.

可见，di可以取的最小值，就是让b第一个大于或等于ai的bj减去ai得到。这里可以用二分计算得到的（否则超时）计算di的最大值则存在一些限制，以最后一个例子为例： a = [10 ,20, 30, 40] b = [22, 33, 33, 55] 考虑d可以取的最大值，如果d1设定为55 - 10，那么这种情况下d4就没有办法取值了，因为只有55大于40，要考虑到这个问题。设置mark[i]标记在序列b中大于等于ai的数值的个数，并用变量cnt计数占用了bi值的数量，如果可以使用bi值的数达到mark[i]，则取在序列b小于当前max_val的值。