题目描述

DBMS（数据库管理系统）开发团队已成功设计出高效的锁管理器，并计划进一步开发。作为团队的一员，您将负责缓冲区管理器的设计。

DBMS 从硬盘读取的数据块会被存储在内存中一组固定数量的预分配缓冲区中。每个缓冲区可容纳一个数据块，其状态可能是：

• 空闲（free）：不包含有效数据。
• 占用（occupied）：存储了数据，并关联一个价值值（worthiness）（1 到 9 的整数）。
• 锁定（locked）：不可被使用或清空，其价值值未定义。

当 DBMS 需要从硬盘读取数据块时，需决定使用哪个缓冲区：

1. 如果存在空闲缓冲区，则直接使用其中一个。
2. 如果没有空闲缓冲区，则需要选择一个占用的缓冲区清空（flush），除非它被锁定。

缓冲区管理算法

为了提高性能，DBMS 采用高级缓冲区管理算法，其核心思想是：

• 连续读取优化：如果硬盘上的多个数据块能连续存储到内存的连续缓冲区，则性能最佳。
• 最小化清空代价：选择清空价值值总和最小的缓冲区序列。

问题定义

给定：

• 缓冲区数量 N（1 ≤ N ≤ 100,000），编号从 1 到 N。
• 请求读取的数据块数量 K（1 ≤ K ≤ 10,000）。
• 缓冲区状态描述（每个缓冲区用单个字符表示）：
  • 0：空闲（价值值 = 0）。
  • 1-9：占用（价值值 = 对应数字）。
  • *：锁定（不可用）。

目标：
找到 K 个连续的未锁定缓冲区（编号 L 到 L+K-1），使得它们的价值值总和最小。如果有多个解，输出最小的 L。如果无法找到满足条件的序列，输出 0。

输入格式

• 第一行：N 和 K（空格分隔）。
• 后续行：缓冲区状态（每行 80 个字符，最后一行可能不足 80 个字符）。

输出格式

• 符合条件的起始缓冲区编号 L，或 0（无解时）。

输入样例 1

100 10
2165745216091853477755800393859785807207523169954341**7363*9*94664808*4777717089
09825185827659480548

输出样例 1

36

题目分类

• 滑动窗口（Sliding Window）
• 前缀和（Prefix Sum）
• 单调队列优化（Monotonic Queue Optimization）

解题思路

1. 预处理：
   • 将锁定缓冲区（*）视为不可用，其余缓冲区的价值值转换为数值（0-9）。
   • 计算前缀和数组，以便快速计算任意区间的价值总和。
2. 滑动窗口：
   • 遍历所有可能的 K 长度窗口，检查是否全为非锁定缓冲区。
   • 使用单调队列优化，快速找到最小和窗口。
3. 输出结果：
   • 若存在解，输出最小 L；否则输出 0。

来源

Northeastern Europe 2000