题意分析

本题是一个缓冲区管理问题，核心需求是：在一组缓冲区中找到连续K个未锁定的缓冲区，使得它们的"价值和"最小。如果有多个符合条件的区间，选择起始位置最小的那个；如果不存在这样的区间，输出0。

具体要求：

• 缓冲区状态由字符表示：'0'-'9'表示占用或空闲（值为0表示空闲），'*'表示锁定
• 需要找到连续K个非锁定缓冲区（即不包含'*'）
• 计算这些缓冲区的价值和（'0'的价值为0，'1'-'9'按字面量计算）
• 若存在多个解，选择起始位置最小的

解题思路

核心问题转化

本质上是一个"滑动窗口"问题：在一个包含锁定标记的序列中，寻找长度为K的合法窗口（无'*'），并计算窗口内的价值和最小值。

算法选择

1. 滑动窗口算法：适用于在数组/序列中寻找固定长度的最优子区间
2. 前缀和优化：在窗口滑动时，通过"去头加尾"快速更新窗口和，避免重复计算

关键步骤

1. 输入处理：读取缓冲区状态，过滤掉换行符
2. 窗口初始化：从左到右遍历，维护一个当前有效窗口
3. 窗口滑动：
   • 遇到'*'时，重置窗口状态（长度和当前和）
   • 否则，扩展窗口长度并累加价值
   • 当窗口长度达到K时，计算当前和并更新最小值
   • 窗口长度超过K时，减去左侧元素的价值（滑动窗口）
4. 结果判断：若未找到合法窗口，输出0；否则输出最优窗口的起始位置

标程

#include <iostream>
#include <cstdio>
#include <string> 
#include <algorithm>
using namespace std;

char s[100010];  // 存储缓冲区状态

int main() {
    int n, k;
    scanf("%d%d", &n, &k);  // 读取缓冲区数量和目标长度
    
    if (n < k) {  // 缓冲区数量不足，直接输出0
        cout << 0 << endl;
        return 0;
    }
    
    int currentLength = 0;  // 当前窗口长度
    int currentSum = 0;     // 当前窗口价值和
    int minSum = 0x7fffffff;  // 最小价值和（初始化为极大值）
    int minPos = 0;  // 最小价值和对应的起始位置
    
    for (int i = 1; i <= n; i++) {
        char ch;
        scanf("%c", &ch);  // 读取单个字符
        
        if (ch == '\n') {  // 跳过换行符
            i--;
            continue;
        }
        
        s[i] = ch;
        
        if (ch == '*') {  // 遇到锁定标记，重置窗口
            currentLength = 0;
            currentSum = 0;
        } else {
            currentLength++;
            int value = ch - '0';  // 转换为数值
            
            if (currentLength > k) {  // 窗口超过目标长度，滑动窗口
                currentSum = currentSum - (s[i - k] - '0') + value;
                
                // 更新最小值
                if (currentSum < minSum) {
                    minSum = currentSum;
                    minPos = i - k + 1;
                }
            } else if (currentLength == k) {  // 窗口刚好达到目标长度
                currentSum += value;
                if (currentSum < minSum) {
                    minSum = currentSum;
                    minPos = i - k + 1;
                }
            } else {  // 窗口尚未达到目标长度，继续累加
                currentSum += value;
            }
        }
    }
    
    // 输出结果：若未找到合法窗口，输出0；否则输出最小起始位置
    cout << (minSum == 0x7fffffff ? 0 : minPos) << endl;
    
    return 0;
}

算法复杂度分析

• 时间复杂度：O(N)，其中N为缓冲区数量。每个字符仅遍历一次，滑动窗口操作均为常数时间。
• 空间复杂度：O(N)，用于存储缓冲区状态数组。

关键逻辑说明

1. 锁定标记处理：遇到'*'时立即重置窗口，确保窗口内不包含锁定缓冲区。
2. 窗口滑动优化：当窗口长度超过K时，通过"减去左侧元素值+加上右侧元素值"更新窗口和，避免重新计算整个窗口。
3. 起始位置计算：窗口起始位置为i - k + 1，其中i为当前处理的字符位置。
4. 边界条件处理：
   • 若N < K，直接输出0（缓冲区数量不足）
   • 若全程未找到合法窗口，minSum保持初始极大值，最终输出0