P1667 数列

题目描述

给定一个长度是nn的数列AA,我们称一个数列是完美的,当且仅当对于其任意连续子序列的和都是正的。现在你有一个操作可以改变数列,选择一个区间[X,Y][X,Y]满足Ax+Ax+1++AY<0      ,    1<X<=Y<nA_x +A_{x+1} +…+ A_Y<0\;\;\;,\;\;1<X<=Y<n,令S=Ax+Ax+1++AYS=A_x +A_{x+1} +…+ A_Y,对于Ax1A_{x-1}AY+1A_{Y+1}分别加上SSAxA_xAYA_Y分别减去SS(如果X=YX=Y就减两次)。问最少几次这样的操作使得最终数列是完美的。

输入格式

第一行一个数nn,以下nn个数。

【数据规模】

对于2020%的数据,满足1N51≤N≤5;

对于100100%的数据,满足1N1051≤N≤10^5; 1Ai23111≤|A_i|≤2^{31}-1

输出格式

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

输入输出样例

输入 #1

1
2
3
4
5
6
5
13
-3
-4
-5
62

输出 #1

1
2

说明/提示

【样例解释】

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

思路

有很多想吐槽的……

不过在此之前先说说做这题的思路。

题目中的任意子序列很容易让人想到前缀和

没错,这题就是要利用前缀和的思想。(窝好像说了些没什么用的bulabula……

对于任意一个区间[x,y],1<X<=Y<n[x,y],1<X<=Y<n,设S=i=xyAiS=\sum\limits_{i=x}^y A_i

那么对于前缀和sumsum来说,每一次关于x,yx,y的操作就是sumx1+S  ,  sumx+SS  ,  sumyS  ,  sumy1S+Ssum_{x-1}+S\;,\;sum_x+S-S\;,\;sum_y-S\;,\;sum_{y-1}-S+S

我们可以注意到,数列中本身就有sumx1+S=sumy  ;  sumyS=sumx1sum_{x-1}+S=sum_{y}\;;\;sum_y-S=sum_{x-1}

所以每次操作,sumx1=sumx1+S=sumy  ;  sumy=sumyS=sumx1sum_{x-1}=sum_{x-1}+S=sum_y\;;\;sum_y=sum_y-S=sum_{x-1}

所以每次操作的实质,就是将sumx1sum_{x-1}sumysum_y进行了替换。

所以,题目就变成了:“一个前缀和数列(sumiNsum_i \in N^*)可任意交换2个数,问使其变为单调递增的数列的最小步数。”

那么就水起来了,离散化一下。

然后:

1
2
3
4
5
for(register int i=1;i<n;i++)
while(a[i]!=i){
ans++;
std::swap(a[i],a[a[i]]);
}

就OK了。

就是这样。

但是……

吐槽

你可能看完我的题解代码之后,再去看别的题解的时候会有些困惑,因为有一些题解或题解评论都提到了几组hack\mathtt{hack}数据。

建议回去认认真真再看看题,认认真真自己手推一下!

提示:对于100100%的数据,满足1N1051≤N≤10^5; 1Ai23111≤|A_i|≤2^{31}-1

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<algorithm>

const int maxn=1e5+10;

int n,a[maxn],t[maxn],ans;

inline int read(){
char ch=getchar();int f=1,r=0;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){r=r*10+ch-'0';ch=getchar();}
return f*r;
}

int main(){
n=read();
for(register int i=1;i<=n;i++){
a[i]=t[i]=a[i-1]+read();
if(a[i]<=0){
printf("-1");
return 0;
}
}
std::sort(t+1,t+1+n);
int l=std::unique(t+1,t+1+n)-t-1;
for(register int i=1;i<=n;i++) a[i]=std::lower_bound(t+1,t+1+l,a[i])-t;
for(register int i=1;i<n;i++)
while(a[i]!=i){
ans++;
std::swap(a[i],a[a[i]]);
}
printf("%d\n",ans);
return 0;
}
文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/09/14/P1667 数列/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论