[C++知识库] [Acwing] 第16场周赛 B.3956. 截断数组

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> [Acwing] 第16场周赛 B.3956. 截断数组 -> 正文阅读

[C++知识库][Acwing] 第16场周赛 B.3956. 截断数组

前言

$t a g :$ 前缀和 二分 思维
传送门 :

题意

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

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

数据范围 $n\in[1,10^5]$

思路

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

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

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

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

然后我们再处理出来 $s u m [i] = = 2 ? (s u m [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;
	
}