农夫约翰在给他编号为 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
样例
输入样例：
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 <iostream>
#include <cstring>
#include <algorithm>
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<<a[i]<<' ';
return 0;
}
}
}
}
return 0;
}
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;i<n-1;i++)b[i]=cin.nextInt();
for(int i=1;i<=n;i++)
{
Arrays.fill(s, 0);
a[0]=i;
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]>0)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 <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int n;
int main()
{
cin>>n;
std::vector<int> b(n+1),a(n+1);
for(int i=1;i<n;i++)cin>>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<int> 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<<a[i]<<" ";
return 0;
}
其他人的解法
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 <iostream>
#include <cstring>
#include <algorithm>
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<n;i++)cin>>b[i];
for(int i=1;i<=n;i++)
{
if(get(i))break;
}
for (int i = 1; i <= n; i ++ )
cout<<a[i]<<' ';
return 0;
}
方法四：dfs
大佬的解法
#include <iostream>
#include <cstring>
#include <algorithm>
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<<a[j]<<" ";
return 0;
}
st[i]=false;
}
}
欢迎留言点赞
嗷嗷嗷
|