移动元素（秋季每日一题 35）

给定一个长度为 $n$ 的正整数数组 $a_1,a_2,\dots ,a_n$。

你需要选择其中一个元素，将其移动至数组中的任意位置（也可以留在原位置）。

我们的目标是，在移动元素操作完成以后，将数组分为前后两个非空部分，并使前一部分的各元素之和等于后一部分的各元素之和。

请问，该目标能否达成？

输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

输出格式
每组数据输出一行结果，目标可以达成，则输出 YES，否则输出 NO。

数据范围
$1\le T\le 20,$
$1\le n\le 10^5,$
$1\le a_i\le 10^9$。
同一测试点内所有 $n$ 的和不超过 $10^5$。

输入样例：

3
3
1 3 2
5
1 2 3 4 5
5
2 2 3 4 5
1
2
3
4
5
6
7

输出样例：

YES
NO
YES
1
2
3

---

分类讨论

1. 要移动的元素的原位置与目的位置都在分割线一边
   则直接找到 $S/2$
2. 要移动的元素的原位置与目的位置在分割线的两边
   则算出前缀和与后缀和
   有 $s[i]-a[k]=S/2$
   $a[k]=s[i]-S/2$
   枚举 $i$ 判断 $a_k$ 是否在 $a[1$ ~ $i]$ 中 存在

#include
#include

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N], b[N];
LL s[N];

bool check(int w[]){
   
    
    for(int i = 1; i <= n; i++) s[i] = s[i-1] + w[i]; 
    if(s[n] % 2) return false;
    
    unordered_set<LL> S;
    S.insert(0);
    for(int i = 1; i <= n; i++){
        
        S.insert(w[i]);
        if(S.count(s[i] - s[n] / 2)) return true;
    }
    
    return false;
}

int main(){
    
    int t;
    scanf("%d", &t);
    
    while(t--){
        
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            b[n-i+1] = a[i];
        }
        
        if(check(a) || check(b)) puts("YES");
        else puts("NO");
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49