Array Recovery题解

· · 题解

读题之后可以惊喜地发现：诶？这不是差分吗？

众所周知差分的逆运算是前缀和。

所以打一个前缀和程序复原就可以了（可以加一个前缀和标签）。

每一个向前递推，如果比它大就只能加，如果小于等于就可加可减，输出 -1 。

贴出代码：

#include<bits/stdc++.h>
using namespace std;
int t[105],l[105];
int main(){
    int x,y,z;
    cin>>x;
    while(x--){
        int y;
        cin>>y;
        bool s=0;
        cin>>l[1];
        t[1]=l[1];
        for(int i=2;i<=y;i++){
            cin>>l[i];
        }
        for(int i=2;i<=y;i++){
            if(l[i]>=t[i-1]||l[i]==0){
                t[i]=(t[i-1]+l[i]);
            }else{
                cout<<-1<<endl;
                s=1;
                break;
            }
        }
        if(s==0){
            for(int i=1;i<=y;i++){
                cout<<t[i]<<' ';
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

然而这个题有个坑点：是非负数列！

即：其中的元素可以为 0 ！

这也是为什么我WA了两次

于是把

l[i]>=t[i-1] //改成 
l[i]>t[i-1]

之后，就可以 \verb!AC! 了。

完整代码