题目链接:https://codeforces.com/contest/1141/problem/C
题意是有一个数组p,为1-n的一个排列,现在有一个q数组,使得每一位qi = pi+1 - pi,现在给出了q数组,让你还原出p数组,如果还原不出p数组输出-1
有两种方法,一种是推出一个关于p1的公式,一种是求一下偏移量。首先说一下求偏移量的方法,我们先令p1为1,然后构造出一个数组,然后找出这个数组中的最小值。因为原p数组应是1-n的排列,所以最小值应该是1,如果不是1的话就会有一个偏移量,然后我们将每个数都加上这个偏移量,然后再看这个数组是否合法就好了。
另一种方法是我们对于q数组求前缀和,可以得到s数组,因为qi = pi+1 - pi,所以可以推出si = pi+1 - p1,又因为p1+p2+p3+p4+...+pn = n * (n + 1) / 2,所以可以得到一个关于p1的式子,(n-1)p1 = p2 + p3 + ... + pn - s1 - s2 - ... - sn-1,就可以求出p1的值了,从而推出整个数组,然后再判断是否合法即可。
AC代码(偏移量):
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int n;
int pre[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d",&pre[i]);
}
int a[maxn];
a[1] = 1;
int ans = 0x3f3f3f3f;
for(int i=1;i<n;i++){
a[i + 1] = a[i] + pre[i];
ans = min(ans, a[i + 1]);
}
ans = min(ans, 1);
int xx = 1 - ans;
map<int,int> ma;
for(int i=1;i<=n;i++){
a[i] += xx;
ma[a[i]] ++;
}
for(int i=1;i<=n;i++){
if(ma[i] != 1){
puts("-1");
return 0;
}
}
for(int i=1;i<=n;i++){
printf("%d ",a[i]);
}
return 0;
}
AC代码(公式):
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
ll pre[200005],s[200005],a[200005];
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%lld",&pre[i]);
}
ll ans = 0;
for(int i=1;i<n;i++){
s[i] = pre[i] + s[i-1];
ans += s[i];
}
map<int,int> ma;
a[1] = (ll)n * (ll)(n + 1) / 2 - ans; // 这里会爆int
a[1] /= n;
ma[a[1]] ++;
for(int i=1;i<n;i++){
a[i + 1] = a[i] + pre[i];
ma[a[i+1]] ++;
}
for(int i=1;i<=n;i++){
if(ma[i] != 1){
puts("-1");
return 0;
}
}
for(int i=1;i<=n;i++){
printf("%lld ",a[i]);
}
return 0;
}