[OpenJude]LGTB学分块

题目描述

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

今天他得到了一个数组，他突然也想把它分块，他想知道，把这个数组分成3块，块可以为空。假设3块各

自的和中的最大值最小

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

输入输出格式

输入格式

输入第一行包含一个整数n 代表数组大小

接下来n 个整数$$a_1,a_1, \cdots , a_n$$，代表数组

对于40% 的数据，$$1 \leq n \leq 10$$

对于70% 的数据，$$1 \leq n \leq 10^3$$

对于100% 的数据，$$1 \leq n \leq 10^5 , 1 \leq a_i \leq 10^7$$

输出格式

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

输入输出样例

输入样例1

5
9 9 8 7 6

输出样例1

17

思路

枚举+二分

枚举第1块，二分剩余的数

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int a[10001];
int n;
long long sum[10001];
long long ans=0;

void halfwork(int i)
{
    long long x,y,z; 
    x=sum[i-1];
    int l=i+1;
    int r=n+1;
    while(l<r-1)
    {
        int mid=(l+r)>>1;
        y=sum[mid-1]-x;
        z=sum[n]-sum[mid-1];
        if(y<=z)    l=mid;
        else    r=mid;
    }
    //mid--->y
        y=sum[l]-x;
    z=sum[n]-sum[l];
        ans=min(ans,max(x,max(y,z)));
    //mid--->z
    y=sum[l-1]-x;
    z=sum[n]-sum[l-1];
        ans=min(ans,max(x,max(y,z)));
}

int main()
{
    freopen("divide.in","r",stdin);
    freopen("divide.out","w",stdout);
    memset(sum,0,sizeof(sum));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    ans=sum[n];
    for(int i=1;i<=n;i++)
        halfwork(i);
    cout<<ans<<endl;
    return 0;
}