题目名称 3980. [POJ 3061]子段和问题
输入输出 subsequence.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试数据 10
题目来源 Gravatarsyzhaoss 于2024-05-28加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:7, 提交:10, 通过率:70%
Gravatar┭┮﹏┭┮ 100 0.161 s 3.90 MiB C++
Gravatar 100 0.163 s 3.90 MiB C++
Gravatarsyzhaoss 100 0.491 s 3.90 MiB C++
Gravatar三玖是我老婆 100 0.596 s 4.35 MiB C++
Gravatarsyzhaoss 100 0.599 s 4.55 MiB C++
Gravatarsyzhaoss 100 0.913 s 4.55 MiB C++
Gravatar黄天乐 100 1.742 s 3.82 MiB C++
Gravatar┭┮﹏┭┮ 80 0.187 s 3.90 MiB C++
Gravatardustsans 0 0.960 s 4.89 MiB C++
GravatardarkMoon 0 2.105 s 3.29 MiB C++
关于 子段和问题 的近10条评论(全部评论)
注意 $0$
Gravatar┭┮﹏┭┮
2024-06-04 15:07 1楼

3980. [POJ 3061]子段和问题

★★☆   输入文件:subsequence.in   输出文件:subsequence.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

给定一个长度为$n$的正整数序列$a_1,a_2,\cdots,a_n$以及一个正整数$S$。

请你编写一个程序求一个长度最小的连续子段,使得子段的和大于等于$S$。

【输入格式】

第一行包含一个整数$T$,表示共有$T$组测试数据。

每组数据的第1行包含整数$n,S$。

第2行包含$n$个正整数$a_1,a_2,\cdots,a_n$。

【输出格式】

对于每组数据,输出一个整数,表示满足条件的最小长度,如果不存在,则输出0

【样例输入】

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

【样例输出】

2
3

【数据规模与约定】

对于$20\%$的数据,$10\leq n\leq 500$。

对于$40\%$的数据,$10\leq n\leq 5000$。

对于$100\%$的数据,$1\leq T\leq 10,10\leq n\leq 10^5,1\leq a[i]\leq 10^4, 1\leq S\leq 10^8$