LGTB 最近在学分块，但是他太菜了，分的块数量太多他就混乱了，所以只能分成3 块 今天他得到了一个数组，他突然也想把它分块，他想知道，把这个数组分成3 块，块可以为空。假设3 块各 自的和中的最大值最小 请输出分完之后3 块中的最大值
输入第一行包含一个整数n 代表数组大小 接下来n 个整数a1, a2, …, an，代表数组 对于40% 的数据，1 n 10 对于70% 的数据，1 n 103 对于100% 的数据，1 n 105, 1 ai 107
输出包含1 个整数，代表分块完成后3 块中的最大值
首先个人认为可以用动态规划做的（虽然我也是个动规蒟蒻 ）然后，果不其然，崩了，但还拿了40：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAX 1500000000 int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-f; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=(s<<3)+(s<<1)+ch-'0'; ch=getchar(); } return s*f; } int max(int x,int y){ return x > y ? x : y; } int min(int x,int y){ return x < y ? x : y; } int n,a[5000005],f[5000005][5];//f[i][j]表示将前i个数分成j段的s最小 int main() { freopen("divide.in","r",stdin),freopen("divide.out","w",stdout); n=read(); for(int i=1;i<=n;i++){ a[i]=read();f[i][1]=f[i-1][1]+a[i]; } for(int i=1;i<=n;i++)f[i][2]=f[i][3]=MAX; for(int i=2;i<=n;i++){ for(int j=1;j<i;j++){ f[i][2]=min(f[i][2],max(f[i][1]-f[j][1],f[j][1])); f[i][3]=min(f[i][3],max(f[i][1]-f[j][1],f[j][2])); } } printf("%d",f[n][3]); fclose(stdout),fclose(stdin); return 0; }接下来，便是正解：二分（大佬啊，赐予我正解吧！）
#include<cstdio> #include<cstring> using namespace std; const int N=5e6+5; int s[N],x,n,smax,ans=2000000000; int find(int x,int l,int r){ if(l>r) return r; int mid=(l+r)/2; if(s[mid]==x) return mid; if(s[mid]>x) return find(x,l,mid-1); return find(x,mid+1,r); } int min(int x,int y){ if(x<y) return x;return y; } int main(){ freopen("divide.in","r",stdin); freopen("divide.out","w",stdout); scanf("%d",&n); s[0]=0; for(int i=1;i<=n;++i){ scanf("%d",&x); s[i]=s[i-1]+x; } int l=0,r=s[n]; while(l<=r){ smax=(l+r)/2; int i=find(smax,1,n); int j=find(smax+s[i],1,n); if(j==i||s[n]-s[j]>smax){ l=smax+1; } else{ ans=min(ans,smax); r=smax-1; } } printf("%d",ans); fclose(stdin);fclose(stdout); return 0; }