奶牛排队拍照

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

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

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

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

在这张纸被偷走之前，奶牛贝茜记录了序列 b1,b2,…,bN−1，对于每一个 1≤i

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

排列 x 字典序小于排列 y，如果对于某个 j，对于所有 i

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

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

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

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

数据范围
2≤N≤103

样例
输入样例：
5
4 6 7 6
输出样例：
3 1 5 2 4
样例解释
a 能够产生 b，因为 3+1=4，1+5=6，5+2=7，2+4=6。

思路一：枚举

感觉就是个暴力，因为从题意来看只要确定第一头剩下的都能确定
则我们只需要枚举第一头即可

(暴力枚举) 实际运行小于 O(n3)

时间复杂度
参考文献
C++ 代码

#include 
#include 
#include 
using namespace std;
const int N = 1e5+10;
int n;
int a[N],b[N],s[N];
int main()
{
    cin>>n;
    bool flag=false;
    for (int i = 0; i < n-1; i ++ )cin>>b[i];
    for (int i = 1; i <= n; i ++ )
    {
        memset(s, 0, sizeof s);
        a[0]=i;//从1开始枚举
        s[i]=1;//标记
        for (int j = 0; j < n-1; j ++ )
        {
            int x=b[j]-a[j];//a[j+1]的可能值
            if(x<=0||s[x])break;
            else 
            {
                a[j+1]=x;//赋值
                s[x]++;
                if(j+1==n-1)//a数组存在,因为是从小开始枚举，此时一定是字典序最小
                {
                    for (int i = 0; i < n; i ++ )
                    cout<

Java 代码

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    public static void main(String args[])  {
      Scanner cin = new Scanner(System.in); 
       int a[]=new int [10100];
       int b[]=new int [10100];
       int s[]=new int [10100]; 
        n=cin.nextInt();
        boolean flag=false;
        for(int i=0;i0)break;
                else 
                {
                    a[j+1]=x;
                    s[x]++;
                    if(j+1==n-1)
                    {
                        for (int k = 0; k < n; k ++ )
                        System.out.print(a[k]+" ");
                        return ;
                    }
                }
            }
        }
    }
}

思路二：set+枚举

公式变形 
b2=a2+a3 b3=a3+a4
b3-b2=a4-a2 a2–>已知 b2-b1=a3-a1–> a3=b2-b1+a1
a数组里不能有重复的元素，那就用set容器存储某些结果

时间复杂度 O(n^2)
参考文献
C++ 代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
int n;
int main()
{
    cin>>n;
    std::vector b(n+1),a(n+1);
    for(int i=1;i>b[i];
    for(int x=1;x<=n;x++)
    {
        a[1]=x,a[2]=b[1]-x;
        for(int i=3;i<=n;i++)
            a[i]=a[i-2]+b[i-1]-b[i-2];
        bool flag=false;
        set s;
        for(int i=1;i<=n;i++)
        if(a[i]>=0&&a[i]<=n)
            s.insert(a[i]);
        if (s.size()==n)
        {
            flag=true;
            break;
        }
        s.clear();
    }
     for(int i=1;i<=n;i++)
        cout<

其他人的解法

Python3 代码

def main():
    n = int(input())
    b = list(map(int, input().split()))

    a = [0 for _ in range(n)]
    visited = [False for _ in range(n + 1)]
    for x in range(1, b[0]):
        a[0] = x
        ok = True
        for i in range(n + 1):
            visited[i] = False
        for i in range(1, n):
            a[i] = b[i - 1] - a[i - 1]
            if 1 <= a[i] <= n and visited[a[i]] == False:
                visited[a[i]] = True
            else:
                ok = False
                break
        if ok == True:
            for x in a:
                print(x, end = " ")
            print()
            return 

if __name__ == "__main__":
    main()

方法三：思路类似 暴力枚举

#include 
#include 
#include 
using namespace std;
const int N = 1e6+10;
int n;
int b[N],a[N];
bool st[N];
bool get(int u)
{
    memset(st, 0, sizeof st);
    st[u]=true;
    a[1]=u;
    for (int i = 1; i < n; i ++ )
    {
        a[i+1]=b[i]-a[i];
        if(a[i+1]<1||a[i+1]>n||st[a[i+1]])return false;
        st[a[i+1]]=true;
    }
    return true;
}
int main()
{
    cin>>n;
    for(int i=1;i>b[i];
    for(int i=1;i<=n;i++)
    {
        if(get(i))break;
    }
    for (int i = 1; i <= n; i ++ )
    cout<

方法四：dfs

大佬的解法

#include 
#include 
#include 
using namespace std;
const int N = 1010;
int n , a[N] , b[N];
bool st[N];
bool dfs(int idx){  //idx为当前枚举的位置
    if(idx==n)return true;//第一次出来的就是字典序最小的了
    for (int i = 1; i <= b[idx]; i ++ ) //枚举a[idx]可能的大小
    if(!st[i] && a[idx-1]+i==b[idx]){   //i这个数字没有出现过 和 前面确定的数字和目前数字和为b[idx]
        st[i]=true;
        a[idx]=i;
        if(dfs(idx+1))return true;
        st[i]=false;
    }
    return false;
}
int main(){
    cin>>n;
    for (int i = 1; i <= n - 1; i ++ )scanf("%d",&b[i]);
    for (int i = 1; i <= b[1]; i ++ ){
        st[i]=true;
        a[0] =i;
        if(dfs(1)){
            for (int j = 0; j < n; j ++ )
                cout<

欢迎留言点赞

嗷嗷嗷