ARC100 D

D - Equal Cut

Time limit : 2sec / Memory limit : 1024MB

Score : 600 points

Problem Statement

Snuke has an integer sequence A of length N.

He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B,C,D and E. The positions of the cuts can be freely chosen.

Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively. Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller. Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Constraints

4≤N≤2×105
1≤Ai≤109
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A1 A2 … AN

Output

Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.

Sample Input 1

Copy

5 3 2 4 1 2

Sample Output 1

Copy

If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3. Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2. We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.

Sample Input 2

Copy

10 10 71 84 33 6 47 23 25 52 64

Sample Output 2

Copy

Sample Input 3

Copy

7 1 2 3 1000000000 4 5 6

Sample Output 3

Copy

999999994

题解：

先做个前缀和，以快速求解区间和

考虑先切中间的那一刀，将整个序列分成左右两块，记为L,R，再将L，R分别切成2块，记为L1，L2，R1，R2

那么，|L1-L2|、|R1-R2|最小时，这样的划分一定是最优的（令L1=L/2+k，L2=L/2-k，R1=R/2+t，R2=R/2-t，显然最大值一定为max{L1,R1}，最小值一定为{L2,R2}，因此k，t增大时，不会使答案更优）

设中间那刀的位置为i，左边的位置为Li，右边的为Ri，注意到i增大时，Li，Ri均单调增大

考虑从小到大枚举i，同时调整Li和Ri，利用Li和Ri的单调性，即可做到O（n）

#include<bits/stdc++.h>
using namespace std;
int n;
long long ans=1e18;
int arr[200005];
long long pre[200005];
long long maxn(long long a,long long b)
{
    return a>b?a:b;
}
long long minx(long long a,long long b)
{
    return a<b?a:b;
}
int main()
{
    scanf("%d",&n);
    pre[0]=0;
    for(int i=1;i<=n;i++)
        {
            scanf("%d",&arr[i]);
            pre[i]=pre[i-1]+(long long)arr[i];            
        }    
    int L=0,R=2;    
    for(int i=2;i<=n-2;i++)
        {
            while(pre[L]<pre[i]-pre[L])
                  L++;
            if(2*pre[L]-pre[i]>pre[i]-2*pre[L-1])
               L--;
            while(pre[R]-pre[i]<pre[n]-pre[R])
                  R++;
            if(2*pre[R]-pre[i]-pre[n]>pre[n]+pre[i]-2*pre[R-1])
               R--;
            long long s1=maxn(pre[L],pre[i]-pre[L]);
            long long s2=maxn(pre[n]-pre[R],pre[R]-pre[i]);
            long long s3=minx(pre[L],pre[i]-pre[L]);
            long long s4=minx(pre[n]-pre[R],pre[R]-pre[i]);
            long long mx=maxn(s1,s2);
            long long mn=minx(s3,s4);
            ans=minx(ans,mx-mn);            
        }
    printf("%lld",ans);        
    return 0;
}

View Code