上海金融网站建设,wordpress自动语言,青岛网站建设及app,flash网站制作文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴一维前缀和一、题目
1、原题链接 3956. 截断数组 2、题目描述 给定一个长度为 n 的数组 a1,a2,…,an。 现在#xff0c;要将该数组从中间截断#xff0c;得到三个非空子…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴一维前缀和一、题目
1、原题链接 3956. 截断数组 2、题目描述 给定一个长度为 n 的数组 a1,a2,…,an。 现在要将该数组从中间截断得到三个非空子数组。 要求三个子数组内各元素之和都相等。 请问共有多少种不同的截断方法 输入格式 第一行包含整数 n。 第二行包含 n 个整数 a1,a2,…,an。 输出格式 输出一个整数表示截断方法数量。 数据范围 前六个测试点满足 1≤n≤10。所有测试点满足 1≤n≤105−10000≤ai≤10000。 输入样例1 4
1 2 3 3输出样例1 1输入样例2 5
1 2 3 4 5输出样例2 0输入样例3 2
0 0输出样例3 0二、解题报告
1、思路分析 思路来源y总每日一题b站视频链接 y总yyds 1数据范围为105需要将时间复杂度控制在 O(nlogn) 以内。 2首先判断所有元素总和是否能被3整除如果不能被3整除说明无法进行分割。如果可以被3整除说明三个子数组的和均为sum/3。 3从前往后依次枚举第二个分割点同时用num记录其前面有多少个位置的前缀和为sum/3。如果第二个分割点位置的前缀和为sum/3*2则说明以该位置为第二分割点的分割方式总共有num种。直到遍历完所有第二分割点可能的位置统计分割方式总数输出即可。
2、时间复杂度
时间复杂度O(n)
3、代码详解
#include iostream
using namespace std;
const int N100010;
typedef long long LL;
int n,a[N],s[N];
LL ans; //注意ans范围最多从10^5-1个位置选两个分割点所以总方案数超出int范围(10^9)要设置成long long
int main(){cinn;int num0; for(int i1;in;i){cina[i];s[i]s[i-1]a[i]; //计算前缀和 }int sums[n];//如果所有元素之和不是3的倍数则无法分割成3个总和相等的子数组if(sum%3!0){cout0;}else{for(int i2;in;i){ //注意i从2到n-1,保证第一个子数组和最后一个子数组最少有一个数if(s[i-1]sum/3) num; //记录从1位置到i位置一共有多少个位置的前缀和为sum/3if(s[i]sum/3*2) ansnum; //如果当前位置满足前缀和sum/3*2说明以当前位置为第二个分割点第一个分割点总共有num个以该位置为第二分割点的总分割数即为num个}coutans;}return 0;
}三、知识风暴 一维前缀和 一维前缀和可以快速计算某一个指定区间内的元素和。 给定数组num[1],num[2],num[3],...,num[n]设s[i]为前i个元素的前缀和,则有s[i]s[i-1]num[i](s[0]0)。若要求区间[a,b]第a个数到第b个数的和包含第a个数和第b个数则为s[b]-s[a-1]。
