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

前言

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

题意

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

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

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

思路

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

对于这种题,一开始就想到的是二分,但是如果对和进行二分的话,会发现不满足单调性,因为 a [ i ] < 0 a[i]n; for(int i=1;i>s[i]; s[i] = s[i-1] + s[i]; } if(s[n]%3){ cout