codeforces：808D. Array Division【二分 + 找规律】

分析

一个东西可以往前or往后放
只要看减去这个东西的前缀和和后缀和是否存在half - num即可
注意：这个前缀和or后缀和不能包含当前数，否则会造成改变

ac code

import sys
from itertools import accumulate
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
preSum = list(accumulate(a, initial = 0))
b = a[::-1]
preSum2 = list(accumulate(b, initial = 0))


tot = sum(a)
if tot % 2 != 0:
    print('NO')
else:
    half = tot // 2
    flag = False
    for i in range(n):
        num = a[i]
        target = half - num
        idx = bisect_left(preSum, target)
        if idx <= i and target == preSum[idx]:
            flag = True
            break
    for i in range(n):
        num = b[i]
        target = half - num
        idx = bisect_left(preSum2, target)
        if idx <= i and target == preSum2[idx]:
            flag = True
            break

    if flag:
        print('YES')
    else:
        print('NO')

总结

前缀和思维 + 去掉一个挪到合适的位置 + 二分查