我要招人

去企业版

首页 > 试题广场 >

子段和

[编程题]子段和

热度指数：1349 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个序列，问你有没有可能重新排列这个序列使得所有长度小于等于 $2$ 的子区间和不等于 $0$ 。

输入描述:

第一行一个  表示序列长度，接下来一行  个数，第  个为 ，表示序列中的第  个数。

。

输出描述:

一行一个字符串。"YES"表示可能重新排列这个序列使得所有长度小于等于  的子区间和不等于 ，反之则输出“NO”。输出不含引号。

示例1

输入

6
34 1345 -3542 -1423 4213 1

输出

YES

说明

不变即可。

示例2

输入

4
1 1 -1 1

输出

NO

说明

无论怎样排列， 总和至少  个  相邻，所以总存在一个和为  的长度为  的子段。

示例3

输入

5
1 5 -1 -5 0

输出

NO

说明

 的存在使得总有一个长度为  的子段和为

算法知识视频讲解

憨憨的竹林

发表于 2026-03-03 00:29:54

什么时候会输出NO？其实观察题目样例我们能很轻松得到答案来着如果序列内有0，那么一定有长度为1的子段和（即元素它自己）是0，直接ban掉另外一种情况，如果序列里只有一个数和他的相反数，那么无论如何排列，都始终无法排序成功使得没有长度2的子段和为0证明的话可以这样想：假设序列里面有m个a和n个-a，那展开全文

kilomatutinal

发表于 2026-03-03 09:27:16

这道题其实挺简单的喵！注意长度小于等于 2 的子区间和不等于 0喵！我们就可以知道相反数不能相邻喵！这就非常简单了喵！假如数组里有0的话，一定NO喵！因为相同的数分散开是不利于满足题意的！所以我们可以把相同数放在一起，看作一个数喵！其实就是去重喵！假设去重后数字大于2的话，就一定是YES！因为有多组展开全文

Guoxu_

发表于 2024-02-21 16:58:38

思路不满足条件的情况存在元素为0。不存在元素为0。这样思考，首先将数组排列，假设数组元素正负交汇处的正数和负数分别为，，而 + 是唯一能等于0的情况，如果此时存在一个元素，则可以将其插入，之间使数组满足条件。综上所述，如果数组只包含两个互为相反数的元素，则不满足条件。代码实现 #i 展开全文

此在Dasein

发表于 2026-03-03 05:46:16

1. 问题分析问题的核心是在给定序列的重排中，消除两类“零和”子区间：长度为 1 的子区间：即序列中的单个元素。若，则该区间和必为 0。长度为 2 的子区间：即相邻的两个元素。若，即两者互为相反数，则该区间和为 0。由于的规模达到，我们需要一个或的算法。 2. 构造展开全文

尖刀笑不停

发表于 2026-03-03 09:01:41

n=int(input()) a=list(set(map(int,input().split()))) if 0 in a: print("NO") else: if len(a)==2 and a[0]+a[-1]==0: print(&qu 展开全文

pandaC222

发表于 2026-03-03 13:24:11

试着想一下不难发现只有两种情况会NO，一种是本身就含有0，另一种是这个序列全是某个数和其相反数，紧接着我们写出代码 #include <iostream> #include<bits/stdc++.h> #include <vector> using namesp 展开全文

AliLexiWalker

发表于 2026-03-03 23:45:30

大概思路就是，随便选一个数看是否存在相反数，并且两者数量加和是否为n就可以判断是否存在所需数组 #include<bits/stdc++.h> using namespace std; using ll=long long; using ull=unsigned long long; 展开全文

如歌丶

发表于 2022-03-28 14:57:18

给定一个序列，问你有没有可能重新排列这个序列使得所有长度小于等于 22 的子区间和不等于 00。 using namespace std; #include <string> long long a[500000]; long long minn,maxn; int main() { 展开全文

YunBaichuan

发表于 2026-03-03 09:39:54

思路：思维题。首先特判0，如果有0存在直接返回False即可；然后计数判断元素种类，如果元素种类不为2，此时必然满足条件，返回True；如果元素种类确实只有两种，那再额外判断一下他们的和是否为0，如果是的话必然无法满足条件，反之满足条件代码： import sys from collections 展开全文

昵称识别不了被气到红温

发表于 2026-03-03 10:47:09

考虑输出NO的情况：已知在长度<=2的字段和为0时输出NO，而长度<=2的字段和为0有以下两种情况：1.某一个元素为0，此时将该元素视为单独的长度<=2的字段。2.序列内只存在两种元素，即n和-n，在推断出以上两种判断条件后，我们对序列内的元素种类进行判断，最后得出结果（我是彩笔补展开全文

问题信息

难度：

5条回答 2收藏 12浏览

子段和

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题