| 题目名称 | 3428. 最长子段 |
|---|---|
| 输入输出 | longsubsequence.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2020-06-29加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：82， 通过率：15.85% | ||||
 lihaoze |
100 | 0.013 s | 2.18 MiB | C++ |
|
三玖是我老婆 |
100 | 0.016 s | 2.90 MiB | C++ |
|
嗨嗨嗨 |
100 | 0.062 s | 4.39 MiB | C++ |
|
Tab↹ |
100 | 0.072 s | 3.48 MiB | C++ |
|
syzhaoss |
100 | 0.072 s | 4.36 MiB | C++ |
|
liuyiche |
100 | 0.073 s | 4.09 MiB | C++ |
|
Tab↹ |
100 | 0.089 s | 4.09 MiB | C++ |
|
Tab↹ |
100 | 0.100 s | 4.09 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.180 s | 15.18 MiB | C++ |
|
梦那边的美好ET |
100 | 0.222 s | 15.18 MiB | C++ |
| 关于 最长子段 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
满足 "前缀和 $\le S$ 的子段的长度" 的 $x$ 不是连续的（即对于一个满足性质的 $x$ ，长度小于 $x$ 的子段的前缀和不一定 $\le S$），所以对于二分的每一个答案 $x$ ，应该判断是否存在一个 $\ge x$ 的子段长度，而不是直接判断 $x$
| ||||
【题目描述】
给定$n$个整数$a_i$，求一个尽可能长的非空连续子段使得子段和$\leq S$。
【输入格式】
第一行两个整数$n,S$。
第二行$n$个整数。
【输出格式】
一个整数，最长非空连续子段的长度。
【样例输入】
6 10 -1 2 7 -4 9 12
【样例输出】
4
【数据范围】
$1\leq n\leq 2\times10^5,-10^9\leq a_i\leq 10^9,1\leq S\leq 10^9$。