题目描述

难度分:$1700$

输入$n(1 \leq n \leq 10^5)$、$l$、$r(1 \leq l \leq r \leq 10^9)$和长为$n$的数组$a(l \leq a[i] \leq r)$，以及一个$1$~$n$的排列$p$。

有两个长为$n$的数组$a$和$b$，元素范围均在$[l,r]$中。数组$a$已经输入给你了，但你不知道$b$。

定义$c[i]=b[i]-a[i]$。已知数组$c$中的元素互不相同，且$c$离散化后的结果是排列$p$。

构造一个符合要求的数组$b$。如果无法构造，输出$-1$。

输入样例$1$

5 1 5
1 1 1 1 1
3 1 5 4 2

输出样例$1$

3 1 5 4 2 

输入样例$2$

4 2 9
3 4 8 9
3 2 1 4

输出样例$2$

2 2 2 9 

输入样例$3$

6 1 5
1 1 1 1 1 1
2 3 5 4 1 6

输出样例$3$

-1

算法

构造

先初始化一个二元组数组$tup$，存储信息$(p[i],i)$，然后将其排序。我们最关键的其实是确定$c$数组，这样就能通过$b[i]=a[i]+c[i]$的关系把$b$数组构造出来。

由于构造出来的$b[i]$需要属于区间$[l,r]$，先让$p[i]=1$的那个位置满足条件，留最大的余地，让$b[i]=l$，此时$c[i]=l-a[i]$，其中$i=tup[0][1]$。然后遍历$i \in [1,n)$，令$pre=c[i]$开始构造其他元素。

初始化$c[i]=pre+1$，分为以下三种情况：

1. 如果$b[i]=a[i]+c[i] \lt l$，说明$c[i]$太小了，让它增加$l-c[i]-a[i]$，这样就能把$b[i]$平移到$l$位置。
2. 如果$b[i]=a[i]+c[i] \gt r$，由于一直都保留最大的余地，使用小的$p$值使构造出来的$b$值尽量比$l$大不了多少，所以肯定无解了。
3. 否则$b[i]$是合法的，不用管。

之后令$pre=c[index]$继续构造剩下的元素。

复杂度分析

时间复杂度

对二元组数组$tup$排序之后，后面的构造过程是线性的，因此整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的$a$、$p$两个数组，额外空间有二元组数组$tup$、$c$数组和最后的答案数组$b$，都是线性空间。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int n, l, r, a[N], p[N], b[N], c[N];

int main() {
    scanf("%d%d%d", &n, &l, &r);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }
    vector<array<int, 2>> tup;
    for(int i = 1; i <= n; i++) {
        tup.push_back({p[i], i});
    }
    sort(tup.begin(), tup.end());
    c[tup[0][1]] = l - a[tup[0][1]];
    int pre = c[tup[0][1]];
    bool ok = true;
    b[tup[0][1]] = a[tup[0][1]] + c[tup[0][1]];
    for(int i = 1; i < n; i++) {
        int index = tup[i][1];
        c[index] = pre + 1;
        if(a[index] + c[index] < l) {
            c[index] += l - c[index] - a[index];
        }else if(a[index] + c[index] > r) {
            ok = false;
        }
        b[index] = a[index] + c[index];
        pre = c[index];
    }
    if(ok) {
        for(int i = 1; i <= n; i++) {
            printf("%d ", b[i]);
        }
        puts("");
    }else {
        puts("-1");
    }
    return 0;
}