AcWing 3816. 移动元素
原题链接
中等
作者:
术
,
2021-08-27 15:10:07
,
所有人可见
,
阅读 248
#include <iostream>
#include <unordered_set>
using namespace std;
//注意本题是只移动一个元素
typedef long long LL;
const int N=1e5+5;
int T,n;
int a[N];
int b[N];//逆序
LL s[N];//前缀和
bool check(int w[]){
unordered_set<LL> us;//这里是LL
for(int i=1;i<=n;i++){
s[i]=s[i-1]+w[i];
}
if(s[n]%2) return false;
for(int i=1;i<=n;i++){
us.insert(w[i]);
if(s[i]==s[n]-s[i])
return true;
//若存在元素s[i]-s[n]/2
if(s[n]%2==0&&us.count(s[i]-s[n]/2)){
return true;
}
}
return false;
}
int main()
{
cin>>T;
while(T--){
cin>>n;
for(int i=1,j=n;i<=n;i++,j--) {
cin>>a[i];
b[j]=a[i];//逆序数组
}
if(check(a)||check(b)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}