首页 > 试题广场 >

喜欢切数组的红

[编程题]喜欢切数组的红

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

$\hspace{15pt}$ 小红有一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ ，她打算将数组切两刀变成三个非空子数组，使得每一个子数组中至少存在一个正数，且每个子数组的和都相等。
$\hspace{15pt}$ 看起来不是很难，所以小红想让你求解，一共有多少种不同的切分方案。

输入描述:

第一行输入两个整数  代表数组中的元素数量。
第二行输入  个整数  代表数组元素。

输出描述:

在一行上输出一个整数，代表切分方案数。

示例1

输入

3
3 3 3

输出

示例2

输入

6
1 1 4 5 1 4

输出

示例3

输入

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

输出

算法知识视频讲解

Python3

123想321

import sys
n=int(input())
nums=list(map(int,input().split()))
start=100000
end=0
total=sum(nums)
all_t=total//3
sum1=[]
sum3=[]
count=0
for i in range(n):
    if nums[i]>0:
        start=min(i,start)
        end=max(i,end)
front=sum(nums[:start])
after=total-sum(nums[:start])
for i in range(start,end):
    front+=nums[i]
    after-=nums[i]
    if front==all_t:
        sum1.append(i)
    if after==all_t:
        sum3.append(i+1)
for i in range(len(sum1)):
    for k in range(len(sum3)):
        if sum1[i]<sum3[k]-1:
            count+=1 
print(count)z

找到第一个正数和最后一个正数的位置，刀砍在这两点之间。遍历一边前后的和，记录和为总体/3的位置，再比较位置，前+1（为第二个数组留空）小于后则计次+1.但是过不了第21组，输出会多10，很纳闷

发表于 2026-03-11 04:20:11 回复(1)

Python3

牛客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)

提交观点

问题信息

动态规划

难度：

2条回答 210收藏 1408浏览

喜欢切数组的红

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

相关试题