拍照

题目

1443. 拍照 - AcWing题库

农夫约翰在给他编号为 1…N 的 N 头奶牛排队拍照。

约翰一开始计划从左向右数第 i 个位置排编号为 ai 的奶牛，他在一张纸上写下了排列 a1,a2,…,aN。

不幸的是，这张纸刚刚被小偷偷走了！

幸好约翰仍然有机会恢复他之前写下的排列。

在这张纸被偷走之前，奶牛贝茜记录了序列 b1,b2,…,bN−1，对于每一个 1≤i<N 满足 bi=ai+ai+1。

基于贝茜的信息，帮助约翰恢复可以产生序列 b 的“字典序最小”的排列 a。

排列 x 字典序小于排列 y，如果对于某个 j，对于所有 i<j 均有 xi=yi，且有 xj<yj（换句话说，这两个排列到某个位置之前都相同，在这个位置上 x 小于 y）。

保证存在至少一个满足条件的 a。

输入格式

输入的第一行包含一个整数 N。

第二行包含 N−1 个空格分隔的整数 b1,b2,…,bN−1。

输出格式

输出一行，包含 N 个空格分隔的整数 a1,a2,…,aN。

数据范围

2≤N≤103

代码

import java.util.*;


public class Main {
    static int N = 100010;
    static int n;
    static boolean f = false;
    static int[] a = new int[1010];
    static int[] b = new int[1010];
    static boolean[] m = new boolean[1010];

    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        for(int i = 1; i < n; i ++)
            b[i] = inScanner.nextInt();
        inScanner.close();
        for(int i = 1; i < b[1]; i ++)
        {
            Arrays.fill(m, false);
            m[i] = true;
            a[1] = i;
            for(int j = 2; j <= n; j ++)
            {
                int t = b[j - 1] - a[j - 1];
                if(t > 0 && t <= n && !m[t])
                {
                    m[t] = true;
                    a[j] = t;
                    f = true;
                }
                else 
                {
                    f = false;
                    break;
                }
            }
            if(f)
                break;

        }
        for(int i = 1; i <= n; i ++)
            System.out.printf("%d ", a[i]);
    }
}