4936. 子序列

题目描述

给定一个长度为 $N$ 的正整数序列 $a_1,a_2,…,a_N$ 以及一个正整数 $S$。

请你找到一个该序列的连续子序列，要求：

• 该子序列内所有元素之和不小于 $S$。
• 该子序列的长度尽可能短。

输出满足条件的连续子序列的最小长度。

输入格式

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

每组数据第一行包含整数 $N,S$。

第二行包含 $N$ 个整数 $a_1,a_2,…,a_N$。

输出格式

每组数据输出一行结果，一个整数，表示满足条件的连续子序列的最小长度，如果不存在，则输出 $0$。

数据范围

$1 \le T \le 10$,
$10 \le N \le 10^5$,
$1 \le S \le 10^8$,
$1 \le a_i \le 10000$

输入样例：

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

输出样例：

2
3

算法

二分+前缀和+滑动窗口内的最小值

二分

假设最终答案为 $res$ ，则表示存在长度为 $res$ 的子序列 、即存在长度小于等于 $res$ 的子序列（将等值性质转化为不等性质），使得子序列之和大于等于 $sum$

上图红点表示所有总和大于等于 $sum$ 的子序列长度

为此我们考虑性质 “$f(x)$：存在长度小于等于 $x$ 的子序列使得子序列之和大于等于 $sum$ ”是否具有二分性质

• 对于任意 $x>res$，一定存在这样的子序列（ $res$ 划分方式即可），满足该性质

• 由于 $res$ 是满足这个性质的最小值，因此对于任意 $x<res$，一定不存在这样的子序列（否则 $res$ 就不是最小值了，与假设矛盾），不满足该性质

因此这个性质具有二分

滑动窗口

判断“是否存在长度小于等于 $k$ 的子序列使得子序列之和大于等于 $sum$”可以使用滑动窗口，枚举 $i$，判断是否存在 $j, i - k \le j \le i - 1$ 使得 $S[i] - S[j] \ge sum$，滑动窗口是单调递增队列

时间复杂度

$O(n\log n)$

• 二分答案 $O(\log n)$

• check() 判断 $O(n)$

视频讲解：LeetCode 862. 和至少为 K 的最短子数组（LeetCode究极班） - AcWing

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int n, sum;
int S[N];
int q[N];

bool check(int k)
{
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++)
    {
        while(hh <= tt && q[hh] < i - k)
            hh ++;
        while(hh <= tt && S[q[tt]] >= S[i - 1])
            tt --;
        q[++ tt] = i - 1;

        if(S[i] - S[q[hh]] >= sum)
            return true;
    }
    return false;
}

int main()
{
    int T;
    scanf("%d", &T);

    while(T --)
    {
        scanf("%d%d", &n, &sum);

        for(int i = 1; i <= n; i ++)
        {
            scanf("%d", &S[i]);
            S[i] += S[i - 1];
        }

        int l = 1, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;

            if(check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        if(l == r && check(l))
            printf("%d\n", l);
        else
            puts("0");
    }

    return 0;
}