题目描述 4297.截断数组
给定一个长度为 n 的数组 d1,d2,…,dn。
现在,要将该数组从中间截断,得到三个子数组(可以为空)。
不妨设第一个子数组包含 a 个元素,第二个子数组包含 b 个元素,第三个子数组包含 c 个元素。
那么三个子数组的各元素之和 sum1,sum2,sum3 依次为:
sum1=∑1≤i≤adi,sum2=∑a+1≤i≤a+bdi,sum3=∑a+b+1≤i≤a+b+cdi。
注意,空数组的各元素之和为 0。
我们希望截断后的三个子数组满足:
sum1=sum3。
满足上一条件的情况下,sum1 尽可能大。
请你计算并输出 sum1 的最大可能值。
显然,本题一定有解,因为可以令 a=0,b=n,c=0。
样例
输入
5
1 3 1 1 4
输出
4
算法:前缀和 + 双指针
思路:先对数组求一边前缀和,用两个指针i, j 表示区间[1, i]的和,区间[j, n]的和
证明单调性:对于sum[i]来说,i增大使得sum[i]增大,对于sum[n] - sum[j - 1]来说,当j 减小,使得该值增大
也就是说我们可以让 j 从 n 出发如果sum[n] - sum[j - 1] < sum[i] 的话,说明 j 一定要减小,得证。
include [HTML_REMOVED]
using namespace std;
const int N = 200010;
typedef long long ll;
ll a[N], s[N];
ll n;
int main ()
{
cin>>n;
for(ll i = 1; i <= n;i )
{
cin>>a[i];
s[i] = s[i - 1] + a[i];
}
ll ans = 0;
ll j = n;
for(ll i = 1; i < n; i )
{
while(j > i + 1 && s[n] - s[j - 1] < s[i])// j > i + 1, 当j = i + 1已经走完整个数组
{
j –;
}
if(s[n] - s[j - 1] == s[i])
{
ans = max(s[i], ans);
}
//if(i == j - 1)break;
/*for(ll j = i + 1; j <= n;j ++)
{
if(s[i] == s[n] - s[j - 1])
{
ans = max(s[i], ans);
}
}*/
}
cout<<ans;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla