LGTB 学分块

总时间限制:: 10000ms
单个测试点时间限制:: 1000ms
内存限制:: 65536kB

描述

LGTB 最近在学分块,但是他太菜了,分的块数量太多他就混乱了,所以只能分成 3 块

今天他得到了一个数组,他突然也想把它分块,他想知道,把这个数组分成 3 块,块可以为空。假设 3 块各自的和中的最大值最小

请输出分完之后 3 块中的最大值

输入

输入第一行包含一个整数 n 代表数组大小
接下来 n 个整数 a1 , a2 , ..., a n ,代表数组

输出

输出包含 1 个整数,代表分块完成后 3 块中的最大值

样例输入

10

2 5 1 4 7 3 6 2 5 1

样例输出

提示

对于 40% 的数据,1 ≤ n ≤ 10
对于 70% 的数据,1 ≤ n ≤ 1e3
对于 100% 的数据,1 ≤ n ≤ 1e5 , 1 ≤ ai ≤ 1e7

先枚举两个区间，然后对其中较大的一个区间进行二分，二分后进行两次比较

 #define LL long long

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const LL INF=0x7fffffffffffffff;

 int n;

 int a;

 LL ans=INF;

 LL f[];

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++) {scanf("%d",&a);f[i]=f[i-]+a;}

     if(n==) {cout<<f[];return ;}

     if(n==) {cout<<max(f[],f[]);return ;}

     for(int i=;i<n;i++)

     {

         int left=i+,right=n;

         while(left+<right)

         {

             int mid=(left+right)>>;

             if(f[mid]-f[i]>f[n]-f[mid]) right=mid;

             else left=mid;

         }

         ans=min(ans,max(max(f[i],f[left]-f[i]),f[n]-f[left]));

         ans=min(ans,max(max(f[i],f[left+]-f[i]),f[n]-f[left+]));

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

LGTB 学分块

最新文章

热门文章