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 }

 

目录
相关文章
|
6月前
|
Python
使用array()函数创建数组
使用array()函数创建数组。
115 3
|
6月前
|
JavaScript 前端开发
总结TypeScript 的一些知识点:TypeScript Array(数组)(下)
一个数组的元素可以是另外一个数组,这样就构成了多维数组(Multi-dimensional Array)。
|
13天前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
|
14天前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
|
1月前
|
存储 JavaScript 前端开发
JavaScript Array(数组) 对象
JavaScript Array(数组) 对象
23 3
|
27天前
|
数据采集 JavaScript 前端开发
JavaScript中通过array.filter()实现数组的数据筛选、数据清洗和链式调用,JS中数组过滤器的使用详解(附实际应用代码)
JavaScript中通过array.filter()实现数组的数据筛选、数据清洗和链式调用,JS中数组过滤器的使用详解(附实际应用代码)
|
2月前
|
Go
Golang语言之数组(array)快速入门篇
这篇文章是关于Go语言中数组的详细教程,包括数组的定义、遍历、注意事项、多维数组的使用以及相关练习题。
27 5
|
3月前
|
Python
PyCharm View as Array 查看数组
PyCharm View as Array 查看数组
77 1
|
4月前
|
索引