区间操作的维护看起来很麻烦,考虑转为点操作的维护。题目中的 \(\sum_{i=l}^r a_i\) 启发我们用前缀和。那么我们考虑每次操作会对前缀和数组 \(s\) 造成怎样的变化。设操作区间为 \([l,r]\),按照题意,会把 \(a_{l-1}\) 和 \(a_{r+1}\) 加上 \(S\),\(a_l\) 和 \(a_r\) 减去 \(S\),那么对于 \(s\) 数组的影响即是把 \(s_{l-1}\) 加上 \(S\),\(a_r\) 减去 \(S\)。
接下来我们考虑 \(S\) 的取值,\(S=\sum_{i=l}^r a_i=s_r-s_{l-1}\),然后我们把这个带过去可得:\(s_{l-1}=s_{l-1}+s_r-s_{l-1}=s_r,s_r=s_r-(s_r-s_{l-1})=s_l\)。
然后就发现这其实就是交换操作。
接下来考虑,我们的目标是使得序列 \(a\) 中所有子段和 \(\gt 0\),容易发现这就是让序列 \(a\) 中所有数都 \(\gt 0\),也就是使前缀和序列 \(s\) 单调递增。
所以,我们的问题转化为了:每次操作可选择一对 \(l,r(1\le l\lt r\lt n)\),然后 \(swap(s_l,s_r)\)。求使得序列 \(s\) 单调递增的最小操作次数。
那这就是个经典问题了,可以用找置换环的方式解决,具体来说,我们记 \(s\) 升序排序之后得到的数组为 \(s'\),记 \(pos_i\) 表示数 \(i\) 在 \(s'\) 中出现的位置。那么我们每次从一个没有访问过的位置开始搜,不断令 \(i=pos_{s_i}\),直到找到一个置换环,即 \(i\) 已经被访问过了,就退出,并令置换环个数 cnt++
。
最终答案就是 \(n-1-cnt\)。不懂这里的置换环操作以及答案由来的选手可以自行搜索“置换环”进行了解。至于为什么是 \(n-1\) 而不是 \(n\),是因为我们每次选择的 \(r\) 必须 \(\lt n\),所以 \(s_n\) 一定是永远都不能参与操作的,直接排除它就好了。
最后的最后,我们来考虑判断无解情况,首先如果 \(s\) 中有相等的数的话就一定不能满足“递增”,于是无解,以及如果出现了 \(s_i\le 0\) 的话也一定无解,因为如果有 \(s_i\le 0\),那么我们把 \(s\) 排完序之后一定有 \(s_1\le 0\),即 \(a_1\le 0\),不满足条件,故无解。
以上这些判断可以合并成:
sort(s+1,s+n);
for(re int i=1;i<=n;i++)
if(s[i]<=s[i-1]){
puts("-1");
return 0;
}
然后这题就做完了。
\(\text{Code:}\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=100100;
int n,a[N],s[N],b[N],mx=-1e18;
unordered_map<int,int>mp;
bitset<N>vis;
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
signed main(){
n=read();
for(re int i=1;i<=n;i++)
a[i]=read(),b[i]=s[i]=s[i-1]+a[i];
sort(s+1,s+n);
for(re int i=1;i<=n;i++)
if(s[i]<=s[i-1]){
puts("-1");
return 0;
}
for(re int i=1;i<n;i++)mp[s[i]]=i;
int cnt=0;
for(re int i=1;i<n;i++){
if(vis[i])continue;
int j=i;
while(!vis[j]){
vis[j]=1;
j=mp[b[j]];
}
cnt++;
}
cout<<n-1-cnt;
return 0;
}
标签:le,数列,int,P1667,置换,lt,操作,我们
From: https://www.cnblogs.com/MrcFrst-LRY/p/17753088.html