华为OD机试_2025 B卷_完美走位（Python，100分）（附详细解题思路）

题目描述

在第一人称射击游戏中，玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。

假设玩家每按动一次键盘，游戏任务会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏任务必定会回到原点，则称此次走位为完美走位。

现给定玩家的走位（例如：ASDA），请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。

请返回待更换的连续走位的最小可能长度。

如果原走位本身是一个完美走位，则返回0。

输入描述
输入为由键盘字母表示的走位s，例如：ASDA

输出描述
输出为待更换的连续走位的最小可能长度。

用例

完美走位调整：最小替换长度求解

核心解题思路

问题分析

题目要求通过替换一段连续走位，使整个走位序列变成"完美走位"（各方向移动步数相同）。关键点：

1. 完美走位要求：A、S、D、W四种移动的数量相等
2. 允许替换任意连续子串为同长度新序列
3. 需要找到最小替换长度

核心策略

滑动窗口法：

1. 统计各方向总步数，计算目标值avg = 总步数/4
2. 确定需要减少的方向：对于超过avg的方向，计算需要减少的数量
3. 使用滑动窗口寻找包含所有多余步数的最小连续子串
4. 该子串长度即为最小替换长度

完整代码实现

def main():
    s = input().strip()
    n = len(s)
    if n % 4 != 0:
        print(0)
        return
    
    # 计算每个方向的总数量
    total_count = {'A':0, 'S':0, 'D':0, 'W':0}
    for char in s:
        total_count[char] += 1
    
    avg = n // 4
    # 计算需要减少的数量（超过avg的部分）
    required = {}
    for char in "ASDW":
        if total_count[char] > avg:
            required[char] = total_count[char] - avg
        else:
            required[char] = 0
    
    # 如果已经是完美走位
    if all(value == 0 for value in required.values()):
        print(0)
        return
    
    # 初始化滑动窗口
    l = 0
    win_count = {'A':0, 'S':0, 'D':0, 'W':0}
    min_len = float('inf')
    
    # 滑动窗口遍历
    for r in range(n):
        # 扩展右边界
        win_count[s[r]] += 1
        
        # 检查是否满足条件
        while (win_count['A'] >= required['A'] and 
               win_count['S'] >= required['S'] and 
               win_count['D'] >= required['D'] and 
               win_count['W'] >= required['W']):
            # 更新最小长度
            min_len = min(min_len, r - l + 1)
            # 收缩左边界
            win_count[s[l]] -= 1
            l += 1
    
    print(min_len)

if __name__ == "__main__":
    main()

算法原理解析

关键步骤

1. 预处理：

   # 计算总步数和平均值
   total_count = {'A':0, 'S':0, 'D':0, 'W':0}
   for char in s:
       total_count[char] += 1
   avg = n // 4

2. 需求计算：

   required = {}
   for char in "ASDW":
       if total_count[char] > avg:
           required[char] = total_count[char] - avg
       else:
           required[char] = 0

3. 滑动窗口核心：

   for r in range(n):
       win_count[s[r]] += 1
       while condition_met():
           min_len = min(min_len, r-l+1)
           win_count[s[l]] -= 1
           l += 1

状态转移

1. 窗口扩展：右指针右移，包含新字符
2. 条件检查：窗口是否包含所有多余步数
3. 窗口收缩：满足条件时左指针右移，寻找更小窗口

复杂度分析

• 时间复杂度：O(n)，仅需遍历字符串一次
• 空间复杂度：O(1)，固定大小的字典存储状态

示例解析

示例1：输入"WASDAASD"

1. 总步数统计：

• A:3, S:2, D:2, W:1
• avg = 8//4 = 2

2. 多余步数计算：

• 需要减少：A:1个

3. 滑动窗口过程：

窗口位置窗口字符窗口内A数是否满足最小长度
[0]W0否∞
[0-1]WA1是min(∞,2)=2
[1-1]A1是min(2,1)=1
[1-2]AS1是min(1,2)=1
...后续窗口均≥1

输出：1

示例2：输入"AAAA"

1. 总步数统计：

• A:4, S:0, D:0, W:0
• avg = 4//4 = 1

2. 多余步数计算：

• 需要减少：A:3个

3. 滑动窗口过程：

窗口位置窗口字符窗口内A数是否满足最小长度
[0]A1否∞
[0-1]AA2否∞
[0-2]AAA3是min(∞,3)=3
[1-3]AAA3是min(3,3)=3

输出：3

总结

关键要点

• 问题转化：将替换问题转化为多余步数包含问题
• 窗口收缩：满足条件时立即收缩窗口寻找更优解
• 边界处理：包含字符串长度检查和完美走位检查

应用场景

1. 游戏操作优化
2. 字符串模式匹配
3. 资源均衡分配
4. 数据流分析

该解法通过滑动窗口高效解决了完美走位问题，直观展示了算法如何将复杂问题转化为可计算模型。代码实现简洁高效，时间复杂度O(n)，空间复杂度O(1)，完全满足题目要求。