[codeForce-1006C]-Three Parts of the Array (简单题)

You are given an array $d_{1}, d_{2}, \dots, d_{n}$

Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array.

Let the sum of elements of the first part be $s u m_{1}$

More formally, if the first part of the array contains $a$

s u m 1 = \sum 1 \leq i \leq a d i,

s u m 2 = \sum a + 1 \leq i \leq a + b d i,

s u m 3 = \sum a + b + 1 \leq i \leq a + b + c d i .

The sum of an empty array is $0$

Your task is to find a way to split the array such that $s u m_{1} = s u m_{3}$

Input

The first line of the input contains one integer $n$

The second line of the input contains $n$

Examples
Input
5
1 3 1 1 4
Output
5
Input
5
1 3 2 1 4
Output
4
Input
3
4 1 2
Output
0
Note
In the first example there is only one possible splitting which maximizes sum1: [1,3,1],[ ],[1,4].

In the second example the only way to have sum1=4 is: [1,3],[2,1],[4].

In the third example there is only one way to split the array: [ ],[4,1,2],[ ].

很简单的一道题，开始的时候想多了，两边同时向里面

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int MAX = 2e5 + 10;
long long n, a[MAX], x;
int main() {

    long long sum1 = 0,sum2 = 0,sum0 = 0;
    memset(a,0,sizeof(a));
    scanf("%d", &n );
    for( int i = 1; i <= n; i++ ) {
        scanf("%d",&a[i]);
    }
    int left = 0, right = n+1;
    while(left<right){
        
        if(sum1>sum2){
            right--;
            sum2 += a[right];
            if(left==right)break;
        }
        if(sum2>sum1){
            left++;
            sum1 += a[left];
            if(left==right)break;
        }
        if(sum1==sum2){
            sum0 = sum1;
            left++;
            right--;
            if(left==right)break;
            sum1+=a[left];
            sum2+=a[right];
        }
        
        
    }
    cout<<sum0<<endl; 
     
    return 0; 
}

秒客网

[codeForce-1006C]-Three Parts of the Array (简单题)

相关文章