AcWing 1090. 绿色通道
宋标 Lv5
  2022-08-18 02:30:55 2022-08-18 02:30    

题目

高二数学《绿色通道》总共有 道题目要抄，编号 ，抄第 题要花 分钟。

小 Y 决定只用不超过 分钟抄这个，因此必然有空着的题。

每道题要么不写，要么抄完，不能写一半。

下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。

这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。

现在，小 Y 想知道他在这 分钟内写哪些题，才能够尽量减轻马老师的怒火。

由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。

输入格式

第一行为两个整数 。

第二行为 个整数，依次为 。

输出格式

输出一个整数，表示最长的空题段至少有多长。

数据范围

,
,

输入样例：

17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5

输出样例：

3

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#define N 50010

using namespace std;

int a[N];
// f[i] 表示前i道题且选择第i道题的所有方案集合，属性: 最短用时
// 状态转移: f[i] = Min(f[ i - m - 1 <= j <= i - 1 ]) + a[i];
// q[]作为单调队列，存储m道题的用时, 队头最小用时
int q[N], f[N]; 
int n, m;

bool check(int limit)
{
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; ++ i)
    {
        // 滑动窗口
        if (q[hh] < i - limit - 1) ++ hh;
        f[i] = f[ q[hh] ] + a[i];
        while (hh <= tt && f[ q[tt] ] >= f[i]) -- tt;
        q[++ tt] = i;
    }

    for (int i = n - limit; i <= n; ++ i)
        if (f[i] <= m)
            return true;

    return false;
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= n; ++ i) cin >> a[i];

    int l = 0, r = n;

    // 二分空题段
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << r << endl;

    return 0;
}
 评论