题解

1. 对数组 $b$ 和 $c$ 进行排序,因为前缀和数组是有序的。

2. 通过前缀和的差分,还原出 $b$ 和 $c$ 代表的原始数组,记为 nums1 和 nums2 。

3. 遍历 nums2 ,找到第一个不存在于 nums1 中的数 $x$ ,设其下标为 $i$:

• 如果 $i=n-1$,说明x是原数组的最后一个数,直接将 $x$ 添加到 nums1末尾即可。
• 如果 $i<n-1$,说明x应该插入到 nums1 中,插入位置就是 nums2[i+1] 在 nums1中的位置。

4. 按照第3步找到的位置,将 $x$ 插入到 nums1 中,得到的 nums1 就是还原后的原数组 $a$。

AC代码

#include <bits/stdc++.h>

using namespace std;


int main () {
    int n;
    cin >> n;
    vector<int>a(n);
    vector<long long>b(n),c(n);
    for (int i = 1 ;i < n; i++) {
        cin >> b[i];
    }
    for (int i = 1  ;i < n; i++) {
        cin >> c[i];
    }
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    for (int i = 0; i < n - 1; ++i) {
        b[i] = b[i+1] - b[i];
        c[i] = c[i+1] - c[i];
    }
    for (int i = 0; i < n ;++i) {
        if (b[i] == c[i]) {
            a[i] = b[i];
        }else {
            if (b[i] == c[i+1]) {
                a[i] = c[i];
                for (int j = i + 1; j < n;++j) {
                    a[j] = b[j-1];
                }
                break;
            } else if (c[i] == b [i+1]){
                a[i] =  b[i];
                for (int j = i + 1; j < n; ++j) {
                    a[j] = c[j -1];
                }
                break;
            }
        }
    }
    for (int i =0 ;i < n; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
}

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] a = new long[n];
        long[] b = new long[n];
        long[] c = new long[n];
        for (int i = 1; i < n; i++) {
            b[i] = scanner.nextLong();
        }
        for (int i = 1; i < n; i++) {
            c[i] = scanner.nextLong();
        }

        Arrays.sort(b);
        Arrays.sort(c);

        for (int i = 0; i < n - 1; i++) {
            b[i] = b[i + 1] - b[i];
            c[i] = c[i + 1] - c[i];
        }

        for (int i = 0; i < n; i++) {
            if (b[i] == c[i]) {
                a[i] = b[i];
            } else {
                if ((i + 1 < n) && b[i] == c[i + 1]) {
                    a[i] = c[i];
                    for (int j = i + 1; j < n; j++) {
                        a[j] = b[j - 1];
                    }
                    break;
                } else if ((i + 1 < n) && c[i] == b[i + 1]) {
                    a[i] = b[i];
                    for (int j = i + 1; j < n; j++) {
                        a[j] = c[j - 1];
                    }
                    break;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

题目描述

小美有一个由$n$个互不相等的正整数构成的数组a，但她一不小心把a弄丢了，他想要重新找到$a$。

好在她并不是一无所有，她还记得以下有关$a$的信息：

1. 他完全记得数组b的样子，并且b是数组 a 删除了某个$a_i$ 后，剩余的部分做前缀和并打乱的结果。

2. 他完全记得数组c的样子，并且c是数组 a 删除了某个 $a_j$ 后，剩余的部分做前缀和并打乱的结果。

（保证两次删除的$a_i$和$a_j$不是同一个a 中的元素）。

请你帮她还原出a数组吧。

补充：前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。

输入描述

输入包含三行。

第一行一个正整数$n\ (3\le n \le 10^5)$，表示数组 a 的长度。

第二行$n-1$个正整数 $b_i (1 \le b_i \le 10^{14})$，表示题中所述数组 b。

第二行 $n-1$ 个正整数 $c_i\ (1 \le c_i \le 10^{14})$，表示题中所述数组 c。

（输入保证有唯一解）

输出描述

输出一行$n$个整数，表示你还原出的 a 数组。

样例

输入

4
8 18 14
15 9 1

输出

1 8 6 4