方法思路

要解决这个问题，我们需要从给定的相邻元素和数组a中还原出原始排列p。排列p的性质是1到n的每个数字恰好出现一次。数组a的元素是相邻两个排列元素的和，即a[i] = p[i] + p[i+1]。我们需要找到满足这一条件的排列p，并且如果有多个解，选择字典序最小的那个。

1. 数学推导：
   • 我们可以将排列p的元素表示为p[i] = c[i] + s[i] * x，其中c[i]是常数项，s[i]是符号项（+1或-1），x是一个待确定的变量。
   • 通过递推关系，我们可以计算出所有c[i]和s[i]的值。
2. 确定x的范围：
   • 由于p[i]必须是1到n之间的整数且不重复，我们可以推导出x的可能取值范围。
   • 对于每个i，根据s[i]的值，可以得到x的上下界约束。
3. 验证解的有效性：
   • 在x的可能取值范围内，尝试每个候选x值，构造排列p并验证其是否满足排列的条件（1到n的唯一数字）。
   • 一旦找到第一个有效的x值（即字典序最小的解），立即输出结果。
4. 优化处理：
   • 使用数组代替集合来标记已使用的数字，以提高效率。
   • 提前终止条件：如果在确定x范围的过程中发现无解可能，立即返回-1。

这种方法通过数学推导和范围限定，有效减少了需要检查的候选解数量，确保了在合理的时间内解决问题。

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int n = Integer.parseInt(br.readLine());
        if (n == 1) {
            out.println(1);
            out.close();
            return;
        }

        int[] a = new int[n-1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n-1; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        // 初始化常数项c和符号项s
        int[] c = new int[n+1];
        int[] s = new int[n+1];
        c[1] = 0;
        s[1] = 1;

        // 计算c和s的递推关系
        for (int i = 2; i <= n; i++) {
            c[i] = a[i-2] - c[i-1];
            s[i] = -s[i-1];
        }

        // 确定x的可能范围
        int xLow = 1;
        int xHigh = n;
        
        for (int i = 1; i <= n; i++) {
            int ci = c[i];
            int si = s[i];
            
            if (si == 1) {
                xLow = Math.max(xLow, 1 - ci);
                xHigh = Math.min(xHigh, n - ci);
            } else {
                xLow = Math.max(xLow, ci - n);
                xHigh = Math.min(xHigh, ci - 1);
            }

            // 提前检测无解情况
            if (xLow > xHigh) {
                out.println(-1);
                out.close();
                return;
            }
        }

        // 寻找有效解
        int[] p = new int[n];
        boolean[] used = new boolean[n+1]; // 使用数组替代Set更高效
        
        for (int x = xLow; x <= xHigh; x++) {
            Arrays.fill(used, false); // 重置used数组
            boolean valid = true;

            for (int i = 1; i <= n; i++) {
                int pi = c[i] + s[i] * x;
                
                if (pi < 1 || pi > n || used[pi]) {
                    valid = false;
                    break;
                }
                
                used[pi] = true;
                p[i-1] = pi;
            }

            if (valid) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    sb.append(p[i]);
                    if (i < n-1) sb.append(" ");
                }
                out.println(sb.toString());
                out.close();
                return;
            }
        }

        out.println(-1);
        out.close();
    }
}

Python

def solve():
    n = int(input())
    if n == 1:
        print(1)
        return
    
    a = list(map(int, input().split()))
    
    # 初始化常数项c和符号项s
    c = [0] * (n + 1)
    s = [0] * (n + 1)
    c[1] = 0
    s[1] = 1
    
    # 计算c和s的递推关系
    for i in range(2, n + 1):
        c[i] = a[i-2] - c[i-1]
        s[i] = -s[i-1]
    
    # 确定x的可能范围
    x_low = 1
    x_high = n
    
    # 计算x的可行范围
    for i in range(1, n + 1):
        ci = c[i]
        si = s[i]
        if si == 1:
            new_low = 1 - ci
            new_high = n - ci
        else:
            new_low = ci - n
            new_high = ci - 1
        x_low = max(x_low, new_low)
        x_high = min(x_high, new_high)
        
        # 提前检测无解情况
        if x_low > x_high:
            print(-1)
            return
    
    # 只需找到第一个有效解（字典序最小）
    p = [0] * n
    for x_candidate in range(x_low, x_high + 1):
        used = [False] * (n + 1)  # 使用数组比set更快
        valid = True
        
        for i in range(1, n + 1):
            pi = c[i] + s[i] * x_candidate
            
            if pi < 1 or pi > n or used[pi]:
                valid = False
                break
            
            used[pi] = True
            p[i-1] = pi
        
        if valid:
            print(' '.join(map(str, p)))
            return
    
    print(-1)

if __name__ == "__main__":
    solve()

C++

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> a(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        cin >> a[i];
    }
    
    // 初始化常数项c和符号项s
    vector<int> c(n + 1, 0);
    vector<int> s(n + 1, 0);
    c[1] = 0;
    s[1] = 1;
    
    // 计算c和s的递推关系
    for (int i = 2; i <= n; ++i) {
        c[i] = a[i - 2] - c[i - 1];
        s[i] = -s[i - 1];
    }
    
    // 确定x的可能范围
    int x_low = 1;
    int x_high = n;
    
    for (int i = 1; i <= n; ++i) {
        int ci = c[i];
        int si = s[i];
        int new_low, new_high;
        
        if (si == 1) {
            new_low = 1 - ci;
            new_high = n - ci;
        } else {
            new_low = ci - n;
            new_high = ci - 1;
        }
        
        x_low = max(x_low, new_low);
        x_high = min(x_high, new_high);
        
        // 无解的情况
        if (x_low > x_high) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    // 在x的可能范围内寻找有效解
    for (int x_candidate = x_low; x_candidate <= x_high; ++x_candidate) {
        vector<int> p;
        unordered_set<int> seen;
        bool valid = true;
        
        for (int i = 1; i <= n; ++i) {
            int pi = c[i] + s[i] * x_candidate;
            
            if (pi < 1 || pi > n || seen.count(pi)) {
                valid = false;
                break;
            }
            
            seen.insert(pi);
            p.push_back(pi);
        }
        
        if (valid) {
            for (int i = 0; i < n; ++i) {
                cout << p[i] << (i < n - 1 ? " " : "");
            }
            cout << endl;
            return 0;
        }
    }
    
    cout << -1 << endl;
    return 0;
}