CF1721C

给你一个升序数组 $a_1,a_2,…,a_n$。你要通过以下步骤去得到数组 $b_1,b_2,…,b_n$ ：

1. 生成数组 $d$，由$n$个非负整数组成。
2. 通过 $b_i=a_i+d_i$ 计算每一个 $b_i$。
3. 给 $b$ 进行升序排序。

你现在又知道了结果 $b$，你要算出每一个 $d_i$ 可能的最小值和最大值（每个 $d_i$ 的最值可以是由不同的数组 $d$ 满足的）。

思路

最小的很好办，对于每个 $a_i$ ，用 $b$ 中第一个比 $a_i$ 大的 $b_{pos}$ 减去 $a_i$ 即 $b_{pos}-a_i$ 即是答案。

最大的比较难搞。

考虑一个问题，若 $a_{n}>b_{n-1}$ ，那么 $b_n$ 只有可能由 $a_n$ 变成，于是 $a_n$ 对应的 $d_n$ 有且仅有 $b_n-a_n$ 。

这是第 $n$ 位的情况。考虑第 $i$ 位，若 $a_i>b_{i-1}$ ，这说明 $b_i$ 到 $b_n$ 只能对应由 $a_i$ 到 $a_n$ 变成，那么 $a_{i-1}$ 最大只能变成 $b_{i-1}$ ，而 $a_i$ 到 $a_n$ 最大都能变为 $b_n$ 。

代码

#include<bits/stdc++.h>
#define N 200010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int T;
int n,a[N],b[N],d[N],minn[N],maxn[N];

int main() {
    T=read();
    while(T--) {
        n=read();
        for(int i=1;i<=n;i++) a[i]=read();
        for(int i=1;i<=n;i++) b[i]=read();
        int pos=1;
        for(int i=1;i<=n;i++) {
            while(a[i]>b[pos]) pos++;
            minn[i]=b[pos]-a[i];
        }  
        pos=n;
        int now=n;
        for(int i=n;i>=1;i--) {
            while(a[i]<=b[pos]) pos--;
            maxn[i]=b[now]-a[i];
            if(pos==i-1) now=i-1;
        }
        for(int i=1;i<=n;i++) printf("%d ",minn[i]);
        printf("\n");
        for(int i=1;i<=n;i++) printf("%d ",maxn[i]);
        printf("\n");
    }    
    system("pause");
    return 0;
}