[Acwing] 第16场周赛 B.3956. 截断数组

前言

t a g : tag : tag: 前缀和 二分 思维

题意

给定一个数组 a [ ] a[] a[],长度 n n n

询问有多少种方法,可以使得数组均分成三份

数据范围 n ∈ [ 1 , 1 0 5 ] nin[1,10^5] n∈[1,105]

思路

根据数据范围,显然是要控制在 n l o g n nlogn nlogn以下的

对于这种题,一开始就想到的是二分,但是如果对和进行二分的话,会发现不满足单调性,因为 a [ i ] < 0 a[i]<0 a[i]<0的情况存在

因此不妨换一个方向进行二分

首先我们可以出来 s u m [ i ] = = ( s u m [ n ] / 3 ) sum[i]==(sum[n]/3) sum[i]==(sum[n]/3)的下标,用于表示一个分组满足条件的下标

然后我们再处理出来 s u m [ i ] = = 2 ∗ ( s u m [ n ] / 3 ) sum[i]==2*(sum[n]/3) sum[i]==2∗(sum[n]/3)的下标,用于处理二个分组条件的下标

我们会发现如果前面两个分组定下来了,那么第三个数组也定下来了

因此我们只再 两个分组满足条件的集合中寻找 有多少个 单一分组满足条件

Code

const int N = 1e5+10;
int n;
int s[N];
vector<int> v1,v2;

void solve(){
          
   
	cin>>n;
	for(int i=1;i<=n;i++){
          
   
		cin>>s[i];
		s[i] = s[i-1] +  s[i];
	}
	
	if(s[n]%3){
          
   
		cout<<0<<endl;
		return;
	}
	
	int avg  = s[n]/3;
	ll res = 0 ;
	
	//枚举第一个分组
	for(int i=1;i+2<=n;i++) 
	if(s[i] == avg) 
	v1.pb(i);
	
	//枚举第二个分组
	for(int  i=2;i+1<=n;i++)
	if(s[i] == 2*avg) v2.pb(i);
	
	//寻找第三个分组
	for(int i=0;i<v1.size();i++){
          
   
		int pos = upper_bound(all(v2),v1[i])-v2.begin();
		 res += v2.size()-pos;
	}
	cout<<res<<endl;
	
}