Array Division

time limit per test 2 second memory limit per test 256 megabytes
Vasya has an array a consisting of positive integer numbers. Vasya wants to divide this array into two non-empty consecutive parts (the prefix and the suffix) so that the sum of all elements in the first part equals to the sum of elements in the second part. It is not always possible, so Vasya will move some element before dividing the array (Vasya will erase some element and insert it into an arbitrary position).

Inserting an element in the same position he was erased from is also considered moving.

Can Vasya divide the array after choosing the right element to move and its new position?

传送门:CF808D

Input

The first line contains single integer n (1≤n≤100000) — the size of the array.
The second line contains n integers a1,a2… an (1≤ai≤1e9) — the elements of the array.

Output

Print YES if Vasya can divide the array after moving one element. Otherwise print NO.

Sample Input

1
2
3
1 3 2

Sample Output

1
YES

题解

因为只能移动一个数字 这题就很简单了
先记录一下前缀和
然后看每个位置的和 有三种情况 等于一半肯定可以
小于一半 那么肯定要从后面移一个数字过来 那么就看后面是否有sum/2-prei
大于一半 同理要看前面是否能往后移一个数字 就看前面是否含有prei-sum/2
这两个都可以分别用一个数组记录每个数出现在最左和最右的位置来实现

总复杂度O(n)

AC code:(不包含输入类)

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.*;  
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int n=sc.nextInt();
long[]shu=new long[n];
long[]pre=new long[n];
int[]last=new int[n];
HashMap<Long,Integer>map=new HashMap<Long,Integer>();
HashMap<Long,Integer>map1=new HashMap<Long,Integer>();
long sum=0;
for(int i=0;i<n;i++){
shu[i]=sc.nextInt();
if(!map.containsKey(shu[i]))
map.put(shu[i],i);
map1.put(shu[i], i);
sum+=shu[i];
if(i>=1){
pre[i]=pre[i-1]+shu[i];
}else{
pre[0]=shu[0];
}
}
long count=0;
boolean flag=false;
if(sum%2!=0)pw.println("NO");
else{
sum/=2;
for(int i=0;i<n;i++){
count+=shu[i];
if(count>=sum){
if(count==sum){
flag=true;
break;
}else{
break;
}
}
}
if(flag){
pw.println("YES");
}else{
for(int i=0;i<n;i++){
if(pre[i]>=sum){
if(map.containsKey(pre[i]-sum)){
if(map.get(pre[i]-sum)<i){
flag=true;
break;
}
}
}else{
if(map1.containsKey(sum-pre[i])){
if(map1.get(sum-pre[i])>i){
flag=true;
break;
}
}
}
}
if(flag)pw.println("YES");
else pw.println("NO");
}
}
pw.flush();
}


}
}