Codeforces Round #547 (Div. 3) C. Polycarp Restores Permutation(思维)
Codeforces Round #547 (Div. 3) C. Polycarp Restores Permutation(思维)
Ch_Zaqdt
发布于 2019-03-22 11:57:34
发布于 2019-03-22 11:57:34
题目链接：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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年03月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读