冯泽来 最近在学分块，但是他太菜了，分的块数量太多他就混乱了，所以只能分成3 块
今天他得到了一个数组，他突然也想把它分块，他想知道，把这个数组分成3 块，块可以为空。假设3 块各
自的和中的最大值最小
请输出分完之后3 块中的最大值
输入
输入第一行包含一个整数n 代表数组大小
接下来n 个整数a1, a2, ..., an，代表数组
对于40% 的数据，1≤n≤10
对于70% 的数据，1≤n≤10的3次方
对于100% 的数据，1≤n≤105, 1≤ai≤10的7次方
样例输入1
10
2 5 1 4 7 3 6 2 5 1
样例输出1
14
先用sum[i]统计1到i的和，最后处理的时候用sum[i]-sun[j-1]就可以得到j到i区间的和了。
然后枚举i点，在后面的区间中用二分求出另一个分界点
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long sum[100005],a[100005];
long long ans=111111111111LL;
long long max(long long a,long long b,long long c)
{
if(a>b&&a>c)return a;
if(b>a&b>c)return b;
return c;
}
int main()
{
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
int left=i+1,right=n+1;
while(left<right-1)
{
int mid=left+right>>1;
if(sum[mid-1]-sum[i-1]<=sum[n]-sum[mid-1])
left=mid;
else right=mid;
}
long long ans1=sum[left-1]-sum[i-1];
long long ans2=sum[n]-sum[left-1];
ans=min(ans,max(sum[i-1],ans1,ans2));
ans1=sum[left]-sum[i-1];
ans2=sum[n]-sum[left];
ans=min(ans,max(sum[i-1],max(ans1,ans2)));
}
cout<<ans;
return 0;
}