农夫约翰在给他编号为 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
样例输入样例：54 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<
欢迎留言点赞
嗷嗷嗷