自动搬运

查看原文

来自洛谷，原作者为

	xiaohuli113 **

搬运于2025-08-24 23:06:31，当前版本为作者最后更新于2025-02-02 20:23:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

序列 $A$ 中各个数字之间的差都与差分序列 $D$ 的每一个数字对应，并且序列 $A$ 的长度为 $N$。值得注意的是，序列 $A$ 的数据范围为 $1 \leq A_i \leq N$。所以，序列 $A$ 中的每一个数字都应该为正整数。题意就是给出序列 $D$，求序列 $A$，可以考虑模拟。

对于序列 $A$ 的初始值，可以选择 $1$，这样相对更方便，那么 $A_{1}$ 的值为 $1$。同理，可以得出 $A_{i} = A_{i-1} + D_{i-1}$。

那么如何判断求出的序列是否唯一呢？我们知道，序列 $A$ 的数据范围为 $1 \leq A_i \leq N$。这就意味着，如果要让序列是唯一的，那么 $1$ 到 $N$ 中的所有数字都必须和序列 $A$ 中的所有数字相匹配。这样的话，如果让序列 $A$ 中的所有数字都减去或加上 $1$ 以达到它们之间的差与序列 $D$ 相匹配是不可能的。因为如果序列中的最大值或最小值超出了指定范围，那么得到的序列当然与条件不符。

说简单点，如果序列 $A$ 的最大值与最小值的差等于 $1$ 和 $N$ 的差，那么该序列唯一。如果不符合这个条件，那么就不是唯一的。至于找一段数列里最小值和最大值的求法，这里就不细说了，毕竟最简单的方法就是进行比较。

最后，如果得出的最小值是非正数怎么处理呢？如果是非正数，那让它变成正数就好了。我们假设最小值 $minn$，如果想让所有数字的值变成 $1$，最快的方式就是让它们加上 $1 - minn$。

#include<bits/stdc++.h>
using namespace std;
int n,d[300050],a[300050];
long long int maxn=1,minn=1;
int main(){
    a[1]=1;//初始值 
    scanf("%d",&n);
    for(int i=1;i<n;i++)scanf("%d",&d[i]);
    for(int i=2;i<=n;i++){
        a[i]=a[i-1]+d[i-1];//计算序列A中每个数字的值 
        if(a[i]<minn)minn=a[i];
        if(a[i]>maxn)maxn=a[i];//通过比较算最大最小值 
    }
    int c=maxn-minn;//最大值和最小值的差 
    if(c!=n-1)printf("-1");
    else{
		for(int i=1;i<=n;i++)printf("%d ",a[i]+1-minn);//让非正数变为正数
	}
    return 0;
}