首页 > 试题广场 >

喜欢切数组的红

[编程题]喜欢切数组的红
  • 热度指数：9308 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
\hspace{15pt}小红有一个长度为 n 的数组 \{a_1,a_2,\dots,a_n\} ，她打算将数组切两刀变成三个非空子数组，使得每一个子数组中至少存在一个正数，且每个子数组的和都相等。
\hspace{15pt} 看起来不是很难，所以小红想让你求解，一共有多少种不同的切分方案。

输入描述:
\hspace{15pt}第一行输入两个整数 n \left( 3 \leqq n \leqq 2 \times 10^5 \right) 代表数组中的元素数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left( -10^9 \leqq a_i \leqq 10^9 \right) 代表数组元素。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表切分方案数。
示例1

输入

3
3 3 3

输出

1
示例2

输入

6
1 1 4 5 1 4

输出

0
示例3

输入

10
0 3 4 2 3 2 1 -1 3 4

输出

2
算法知识视频讲解
添加回答
Python3
牛客348448733号头像 牛客348448733号
n = int(input())
a = list(map(int, input().split()))
total = sum(a)

if total % 3 != 0:
    print(0)
    exit()

target = total // 3

# Step 1: 后缀标记（判断是否可以作为合法“第三段”）
suf = [0] * n
suffix_sum = 0
has_pos = False
for i in range(n-1, -1, -1):
    suffix_sum += a[i]
    if a[i] > 0:
        has_pos = True
    if suffix_sum == target and has_pos:
        suf[i] = 1

# Step 2: 后缀和数组，suf[i] 表示 i 到末尾有多少合法“第三段”起点
for i in range(n-2, -1, -1):
    suf[i] += suf[i+1]

# Step 3: 正向处理第一段，同时跟踪中间段是否含正数
cnt = 0
prefix_sum = 0
mid_sum = 0
has_prefix_pos = False
has_mid_pos = False

for i in range(n-2):  # 第一刀最多切到 n-3
    prefix_sum += a[i]
    if a[i] > 0:
        has_prefix_pos = True
    if prefix_sum == target and has_prefix_pos:
        # 初始化中段判断
        mid_sum = 0
        has_mid_pos = False
        # 从 i+1 扫一遍作为中间段，尝试找第二刀位置
        for j in range(i+1, n-1):
            mid_sum += a[j]
            if a[j] > 0:
                has_mid_pos = True
            if mid_sum == target and has_mid_pos:
                # 第三段必须从 j+1 开始
                cnt += suf[j+1]
                break  # 只要找到第一个合法中间段就可以，避免重复计算
print(cnt)

发表于 2025-07-18 00:42:21 回复(0)
提交观点

问题信息

动态规划
难度：
1条回答 663浏览

热门推荐

相关试题

喜欢切数组的红

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号