1090 绿色通道（二分 + 单调队列优化）

小灰灰 2022-08-28 09:46 183阅读 0赞

**1. 问题描述：**

高二数学《绿色通道》总共有 n 道题目要抄，编号 1,2,…,n，抄第 i 题要花 ai 分钟。小 Y 决定只用不超过 t 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。现在，小 Y 想知道他在这 t 分钟内写哪些题，才能够尽量减轻马老师的怒火。由于小 Y 很聪明，你只要告诉他最长的空题段至少有多长就可以了，不需输出方案。

**输入格式**

第一行为两个整数 n，t。第二行为 n 个整数，依次为 a1，a2，…，an。

**输出格式**

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

数据范围

0 < n ≤ 5 × 10 ^ 4，  
0 < ai ≤ 3000，  
0 < t ≤ 10 ^ 8

**输入样例：**

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

**输出样例：**

3  
来源：[https://www.acwing.com/problem/content/1092/][https_www.acwing.com_problem_content_1092]

**2. 思路分析：**

分析题目可以知道这道题目属于最大最小问题，所以我们可以考虑**二分**来解决，先判断是否可以使用二分来解决；能够使用二分的前提是通过某种枚举的策略使得每一次可以将答案确定在mid的左边还是右边，可以发现我们可以枚举当前连续的空题数目，判断在时间t之内是否可以完成，如果可以完成说明可以完成更多的题目，那么答案应该在左边否则答案在右边，也即空题的数目可以更少，通过这样一种枚举的策略可以使得答案唯一确定在某个范围，所以可以通过二分来解决的，所以关键在二分的时候如何判断在最多有mid个空题的时候是否能够完成呢？可以发现与[1089题烽火台][1089]的题目的本质是一模一样的，在m个连续的烽火台中至少有一个发出信号的烽火台，所以我们利用1089题的思路即可，使用**单调队列**来优化，单调队列一个很麻烦的点是需要考虑边界的问题，但是我们可以通过画图来确定是否可以取到对应的边界。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 单调队列优化的过程的过程
        def check(self, k: int, n: int, t: int, w: List[int]):
            q = [0] * (n + 1)
            hh, tt = 0, 0
            f = [0] * (n + 1)
            for i in range(1, n + 1):
                # 更新一下队头的指针, 画图比较好理解
                if q[hh] < i - k - 1: hh += 1
                f[i] += f[q[hh]] + w[i]
                while hh <= tt and f[q[tt]] >= f[i]: tt -= 1
                tt += 1
                q[tt] = i
            # 只要有一段满足说明就满足条件
            for i in range(n - k, n + 1):
                if f[i] <= t: return True
            return False
    
        def process(self):
            n, t = map(int, input().split())
            w = [0] + list(map(int, input().split()))
            l, r = 0, n
            while l < r:
                mid = l + r >> 1
                # 满足说明可以超更多的题目所以空格的数目应该减少
                if self.check(mid, n, t, w):
                    r = mid
                else:
                    l = mid + 1
            return l
    
    
    if __name__ == '__main__':
        print(Solution().process())

[https_www.acwing.com_problem_content_1092]: https://www.acwing.com/problem/content/1092/
[1089]: https://blog.csdn.net/qq_39445165/article/details/120626796