P1667 数列

题目描述

给定一个长度是n的数列A，我们称一个数列是完美的，当且仅当对于其任意连续子序列的和都是正的。现在你有一个操作可以改变数列，选择一个区间[X,Y]满足Ax +Ax+1 +…+ AY<0,1<X<=Y<n，令S=Ax +Ax+1 +…+ AY，对于Ax-1和AY+1分别加上S，Ax和AY分别减去S（如果X=Y就减两次）。问最少几次这样的操作使得最终数列是完美的。

输入输出格式

输入格式：

第一行一个数n，以下n个数。

【数据规模】

对于20%的数据，满足1≤N≤5;

对于100%的数据，满足1≤N≤10^5; 1≤|A[i]|≤2^31-1。

输出格式：

一个数表示最少的操作次数，如果无解输出-1。

输入输出样例

输入样例#1：

输出样例#1：

说明

【样例解释】

首先选择区间[2,4],之后数列变成1,9，-4,7,50，然后选择[3,3]，数列变成1,5,4,3,50

Solution：

　　本题贼有意思。

　　用$s_i$表示$i$的前缀和，那么$s_y-s_{x-1}=T$表示的就是区间$[x,y]$的和，然后我们按照题目中的操作去搞，$a_{x-1}+T,a_{x}-T,a_{y}-T,a_{y+1}+T$，不难发现$s_x,s_y$实际上不变，然后因为$s_y=s_{x-1}+T$则操作等价于交换了$s_{x-1},s_{y}$两值。我们要使得$a_i$均为正数，就得让前缀和单调上升，那么很显然当$s_i\leq 0$或者$s_i=s_j,i\neq j$时无解，由于我们只关心前缀和的大小而非具体的值，所以直接对其离散化，然后就是建边统计一下各个环内的交换次数就好了。

代码：

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)

using namespace std;

const int N=2e5+;

int n,cnt,ans,to[N],net[N],h[N];

ll *q[N],s[N];

bool vis[N];

il int gi(){

    int a=;char x=getchar();bool f=;

    while((x<''||x>'')&&x!='-')x=getchar();

    if(x=='-')x=getchar(),f=;

    while(x>=''&&x<='')a=(a<<)+(a<<)+x-,x=getchar();

    return f?-a:a;

}

il bool cmp(const ll *a,const ll *b){return *a < *b;}

il void add(int u,int v){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt;}

il void dfs(int u){

    for(int i=h[u];i;i=net[i])

        if(!vis[to[i]]) vis[to[i]]=,ans++,dfs(to[i]);

}

int main(){

    n=gi();

    For(i,,n) {

        s[i]=s[i-]+gi(),q[i]=&s[i];

        if(s[i]<=)puts("-1"),exit();

    }

    sort(q+,q+n+,cmp);

    ll lst=-;

    For(i,,n)

        if(*q[i]!=lst) lst=*q[i],*q[i]=++cnt;

        else *q[i]=cnt,puts("-1"),exit();

    For(i,,n) if(i!=s[i]) add(i,s[i]);

    For(i,,n) if(!vis[i]) vis[i]=,dfs(i);

    cout<<ans;

    return ;

}

巴特西

P1667 数列

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章