当前位置：首页 > news >正文

[贪心]Min-Max Array Transformation Codeforces1721C

news 来源：原创 2024/4/29 6:23:38

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

Create an array dd consisting of nn arbitrary non-negative integers.
Set bi=ai+dibi=ai+di for each bibi.
Sort the array bb in non-descending order.

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

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

Input

The first line contains the single integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of arrays aa, bb and dd.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109; ai≤ai+1ai≤ai+1) — the array aa in non-descending order.

The third line contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤1091≤bi≤109; bi≤bi+1bi≤bi+1) — the array bb in non-descending order.

Additional constraints on the input:

there is at least one way to obtain the array bb from the aa by choosing an array dd consisting of non-negative integers;
the sum of nn doesn't exceed 2⋅1052⋅105.

Output

For each test case, print two lines. In the first line, print nn integers dmin1,dmin2,…,dminnd1min,d2min,…,dnmin, where dminidimin is the minimum possible value you can add to aiai.

Secondly, print nn integers dmax1,dmax2,…,dmaxnd1max,d2max,…,dnmax, where dmaxidimax is the maximum possible value you can add to aiai.

All dminidimin and dmaxidimax values are independent of each other. In other words, for each ii, dminidimin is just the minimum value among all possible values of didi.

Example

input

2 3 5

7 11 13

1000

5000

1 2 3 4

10 20 30 40

22 33 33 55

output

5 4 2

11 10 8

4000

0 0 0 0

12 2 3 15

23 13 3 15

题意： 给出一个数组a和数组b，可以通过给每个ai增加一个非负数来得到数组b，问每个ai最少和最多能增加多少。

分析： 题目保证一定能从a转到b，所以对于每个ai都可以让它们增到b中第一个大于等于ai的值这样一定是符合题意的最小增量，这里面有一点贪心的思想，而ai最大增量求法稍麻烦些，同样是贪心的思想，对于比ai大的值可以让它们取第一个大于等于其自身的值，然后b中没被取的最大的值就是答案，实现起来还是有点难的，首先设置一个b数组的下标pos，初始值为n，它后面的值一定都被取过了，所以从大到小遍历a数组时，对于某个ai它最大能变成b[pos]，而pos是动态变化的，每当从b数组中访问过一个值后就需要更新一下pos值，将pos减至后面全部被访问过，而第pos个值未被访问，这个过程看似是在循环里面套循环，实际上pos最多减到1，所以也就执行n次。另外对于a为1 2 3，b为4 5 6的情况，会访问到已经访问了的值，而我们每次访问只能访问未访问的值，所以还需要一个jump数组，表示从i需要增加jump[i]才是i之后第一个未访问的值，这样整体就是O(nlogn)的了，具体细节见代码。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;
//最小增量就是找b中最近的 
//最大增量就是比它大的都取最近的，然后取空出来的最大的
int a[200005], b[200005], mn[200005], mx[200005], jump[200005];
bool flag[200005];
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n;
		scanf("%d", &n);
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			flag[i] = false;
			jump[i] = 0;
		}
		for(int i = 1; i <= n; i++)
			scanf("%d", &b[i]);
		int pos = n;//维护一个指针，标志其之后都是连续的1 
		for(int i = n; i >= 1; i--){
			int t = lower_bound(b+1, b+n+1, a[i])-b;
			mn[i] = t;
			mx[i] = pos;
			if(!flag[t]){
				flag[t] = true;
				jump[t] = jump[t+1]+1;
				while(flag[pos]) pos--;
			}
			else{//找到未访问过的最小的 
				int cpy = t;
				while(flag[t]) t += jump[t];
				flag[t] = true;
				jump[cpy] = t-cpy+1;
				while(flag[pos]) pos--;
			}
		}
		for(int i = 1; i <= n; i++)
			printf("%d ", b[mn[i]]-a[i]);
		puts("");
		for(int i = 1; i <= n; i++)
			printf("%d ", b[mx[i]]-a[i]);
		puts("");		
	}
    return 0;
}