题目描述

难度分:$1300$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$k(1 \leq k \leq 10^9)$和长为$n$的数组 $a(1 \leq a[i] \leq 10^4)$，长为$n$的数组$h(1 \leq h[i] \leq 10^9)$。

选一个子区间$[L,R]$，对于$[L,R-1]$内的$i$，满足$h[i]$是$h[i+1]$的倍数，且$a[L]+a[L+1]+…+a[R]$不超过$k$。

输出子区间长度$R-L+1$的最大值。如果没有这样的子区间，输出$0$。

输入样例

5
5 12
3 2 4 1 8
4 4 2 4 1
4 8
5 4 1 2
6 2 3 1
3 12
7 9 10
2 2 4
1 10
11
1
7 10
2 6 3 1 5 10 6
72 24 24 12 4 4 2

输出样例

3
2
1
0
3

算法

动态规划

先做一个简单的线性DP，相当于预处理。

状态定义

$dp[i]$表示以$i$位置开头且满足$h[i]|h[i+1]$（$|$为整除符号，$a|b$表示$b$能被$a$整除），能够往右延伸的最大长度。

状态转移

如果$h[i]|h[i+1]$，就进行状态转移$dp[i]=dp[i+1]+1$，否则$dp[i]=1$。

二分

考虑到$a[i] \geq 1$，所以对于某个固定的子数组左端点$l$，子数组一定是越长和越大，这就有了单调性。因此遍历$l \in [1,n]$，二分找到满足$\Sigma_{i=l}^{r}a[i] \leq k$的最远$r$，对每个$l$维护$r-l+1$的最大值即可得到最终答案。这时候上面的预处理就有了作用，二分的范围就是$r \in [l,l+dp[l]-1]$。

复杂度分析

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int T, n, k, a[N], h[N], s[N], dp[N];

void solve() {
    dp[n] = 1;
    for(int i = n - 1; i >= 1; i--) {
        if(h[i] % h[i + 1] == 0) {
            dp[i] = dp[i + 1] + 1;
        }else {
            dp[i] = 1;
        }
    }
    int ans = 0;
    for(int l = 1; l <= n; l++) {
        int r = l + dp[l] - 1;
        int low = l, high = r;
        while(low < high) {
            int mid = low + high + 1 >> 1;
            if(s[mid] - s[l - 1] <= k) {
                low = mid;
            }else {
                high = mid - 1;
            }
        }
        if(s[high] - s[l - 1] <= k) {
            ans = max(ans, high - l + 1);
        }
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &h[i]);
        }
        solve();
    }
    return 0;
}