题目描述
数据结果超int开long long,对第二刀枚举,则第一刀符合条件保存在cnt中
第二刀符合条件则把cnt放进res中输出
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
const int N = 100005;
LL s[N];
int cnt=0;
int main()
{
cin>>n;
s[0]=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
s[i]+=s[i-1]+x;
}
if(s[n]%3!=0)
cout<<0<<endl;
else
{
LL res=0;
for(int j=2;j<n;j++)
{
if(s[j-1]==s[n]/3) cnt++;
if(s[j]==s[n]/3*2) res+=cnt;
}
cout<<res<<endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla