CF1141C Polycarp Restores Permutation

Posted by

题目链接:http://codeforces.com/contest/1141/problem/C

思路:

p数组依次表示,设p_1x,则p_2=p_1+(p_2-p_1)=x+q_1p_3=p_2+(p_3-p_2)=x+q_1+q_2,即可推出p_n=p_{n-1}+q_{n-1}=x+ \sum_{i=1}^{n-1}{q_i}

现在唯一未知的量是x,因为p数组的排序是没有影响的,设q的前缀和数组为c,则一定存在一个整数x,满足x+c_{min}=1,则x=1-c_{min}。可以O(n)求出最小值,然后求出整个数组即可。

至于无解情况,判断p_i (i \in [1,n])是否\in [1,n],以及是否满足题意即可。

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
typedef long long ll;
static const ll INF=1<<30;
static const int MAXN=200050;
using namespace std;
ll n,x,X,sum,q[MAXN],Min,p[MAXN];
bool flag;
set<ll> s;
inline int read(){
    int x=0;
    bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        q[i]=read();
        sum+=q[i];
        Min=min(Min,sum);
    }
    p[1]=1-Min;
    s.insert(p[1]);
    for(int i=2;i<=n;i++){
        p[i]=p[i-1]+q[i-1];
        s.insert(p[i]);
        if(p[i]<1||p[i]>n){
            flag=true;
            break;
        }
    }
    if(p[1]<1||p[1]>n||flag||(int)s.size()!=n) printf("-1\n");
    else{
        for(int i=1;i<=n;i++) printf("%d ",p[i]);
    }
    return 0;
}

 

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注