移動元素（秋季每日一題 35）

給定一個長度為 的正整數數組 。

你需要選擇其中一個元素，将其移動至數組中的任意位置（也可以留在原位置）。

我們的目标是，在移動元素操作完成以後，将數組分為前後兩個非空部分，并使前一部分的各元素之和等于後一部分的各元素之和。

請問，該目标能否達成？

輸入格式

第一行包含整數 ，表示共有

每組資料第一行包含整數 。

第二行包含 個整數 。

輸出格式

每組資料輸出一行結果，目标可以達成，則輸出 ​​

​YES​

​​，否則輸出 ​

​NO​

​。

資料範圍

。

同一測試點内所有 的和不超過 。

輸入樣例：

3
3
1 3 2
5
1 2 3 4 5
5
2 2 3 4 5      

YES
NO
YES      

1. 要移動的元素的原位置與目的位置都在分割線一邊

   則直接找到

2. 要移動的元素的原位置與目的位置在分割線的兩邊

   則算出字首和與字尾和

   有

   枚舉 判斷 是否在 ~

#include<iostream>
#include<unordered_set>

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;
}