题目描述

blablabla

样例

 自己复习用，非题解，请谅解！

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 50010;
int nums[N], q[N];
int f[N];
int n, k;

bool check(int x)
{
    memset(q, 0, sizeof q);
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (hh <= tt && q[hh] < i - x - 1) hh ++;
        f[i] = f[q[hh]] + nums[i];
        while (hh <= tt && f[q[tt]] >= f[i]) tt --;
        q[++ tt] = i;
    }
    for (int i = n - x; i <= n; i ++)
        if (f[i] <= k) return true;
    return false;
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) scanf("%d", &nums[i]);
    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla