[1001]最长的区段 | 我们的源代码

Description

现在有一个有n(1<=n<=100000)个正整数的数列ai(1<=ai<=32768), 请你从中找出最长的一段连续序列,使得这段序列中所有元素的和不超过k(1<=k<=109)。输出最长的长度。

Input

输入包含多组样例。
每组样例包含两行,其中第一行包含两个整数n和k,第二行包含n个整数ai。
当接收到n=k=0时输入结束,两个0是结束标记,不是一组测试样例。

Output

对于每组样例,输出一行,包含一个整数,代表最长的长度。

Sample Input

6 10
3 4 3 2 1 6
0 0

Sample Output

4

Hint

题解

#include "bits/stdc++.h"
using namespace std;
int arr[100010];
int main()
{
    while (1)
    {
        int n, k;
        scanf("%d %d", &n, &k);
        if (n == 0 && k == 0)
            return 0;
        int sum = 0;
        int max = 0;
        int res = 0;
        memset(arr, 0, sizeof(arr));

        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
            sum += arr[i];
            max++;
            while (sum > k)
            {
                max--;
                sum -= arr[i - max];
            }
            if (max > res)
                res = max;
        }
        printf("%d\n", res);
    }
}

CC BY-SA 4.0 [1001]最长的区段 | 我们的源代码 by 小小泥娃的部落格 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论