Educational Codeforces Round 21 D.Array Division(二分)

简介: D. Array Division time limit per test:2 seconds memory limit per test:256 megabytes input:standard input output:standard output ...

D. Array Division

time limit per test:2 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output

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?

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 ≤ 109) — the elements of the array.

Output

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

Examples
Input
3 
1 3 2
Output
YES
Input
5 
1 2 3 4 5
Output
NO
Input
5 
2 2 3 4 5
Output
YES
Note

In the first example Vasya can move the second element to the end of the array.

In the second example no move can make the division possible.

In the third example Vasya can move the fourth element by one position to the left.

题目链接:http://codeforces.com/contest/808/problem/D

题意:在数组中移动一个数 使得分组可以分割成两个数组 使得两个数组之和相等

分析:

首先分两种情况
1. 往后面移动一个数到前面  (维护前缀和 看看后面有没有符合条件的数)
2. 移掉一个数            (移掉第i个数 看看连续的数能不能符合条件) 

用二分做,观摩观摩

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=100010;
 5 ll s[N],a[N],sum;
 6 int n;
 7 bool find(int l,int r,ll x)
 8 {
 9     while(l<=r)
10     {
11         int mid=(l+r)/2;
12         if(s[mid]==x)
13             return 1;
14         if(s[mid]<x)
15             l=mid+1;
16         else r=mid-1;
17     }
18    return 0;
19 }
20 int main()
21 {
22     scanf("%d",&n);
23     for(int i=1;i<=n;i++)
24     {
25         scanf("%lld",&a[i]);
26         sum+=a[i];
27         s[i]=s[i-1]+a[i];//求前缀和
28     }
29     if(sum&1)
30     {
31         cout<<"NO"<<endl;
32         return 0;
33     }
34     sum/=2;
35     for(int i=1;i<=n;i++)
36     {
37         if(find(i+1,n,sum+a[i])||find(1,i-1,sum-a[i]))
38         {
39             cout<<"YES"<<endl;
40             return 0;
41         }
42     }
43     cout<<"NO"<<endl;
44     return 0;
45 }

 

目录
相关文章
|
5月前
|
Python
使用array()函数创建数组
使用array()函数创建数组。
86 3
|
5月前
|
JavaScript 前端开发
总结TypeScript 的一些知识点:TypeScript Array(数组)(下)
一个数组的元素可以是另外一个数组,这样就构成了多维数组(Multi-dimensional Array)。
|
5月前
|
存储 JavaScript 前端开发
总结TypeScript 的一些知识点:TypeScript Array(数组)(上)
数组对象是使用单独的变量名来存储一系列的值。
|
1天前
|
存储 JavaScript 前端开发
JavaScript Array(数组) 对象
JavaScript Array(数组) 对象
11 3
|
1月前
|
Go
Golang语言之数组(array)快速入门篇
这篇文章是关于Go语言中数组的详细教程,包括数组的定义、遍历、注意事项、多维数组的使用以及相关练习题。
21 5
|
2月前
|
Python
PyCharm View as Array 查看数组
PyCharm View as Array 查看数组
52 1
|
3月前
|
索引
|
4月前
|
存储 安全 算法
C++的内置数组和STL array、STL vector
C++的内置数组和STL array、STL vector
|
3月前
|
JavaScript API 索引
JS【详解】Set 集合 (含 Set 集合和 Array 数组的区别,Set 的 API,Set 与 Array 的性能对比,Set 的应用场景)
JS【详解】Set 集合 (含 Set 集合和 Array 数组的区别,Set 的 API,Set 与 Array 的性能对比,Set 的应用场景)
50 0