题解：P11332 [NOISG 2020 Finals] Labels

xiaohuli113 · 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;
}