06_Ad_Hoc_Problems_Ad_Hoc问题

Ad Hoc Problems Ad Hoc 问题

什么是 Ad Hoc 问题？

Ad Hoc 问题是一类没有固定算法模式的题目，通常只需要直接模拟题意或者进行简单的逻辑推理就能解决。这类问题的特点是没有通用的解题模板，需要根据每个问题的具体情况灵活处理。

Ad Hoc 问题的特点

1. 没有固定模式：不需要复杂的算法或数据结构
2. 题意驱动：关键在于正确理解题目要求
3. 简单直接：通常只需要模拟或简单逻辑
4. 技巧性强：虽然思路简单，但需要一定的技巧

适用场景

• 规则明确但细节繁杂的题目
• 需要特定数据结构的题目
• 直接模拟即可解决的问题

---

经典例题：Photo Shoot 2 (USACO Bronze)

题目描述

https://usaco.org/index.php?page=viewproblem2&cpid=1237

给定两个长度为 N 的排列 a 和 b。每次操作可以将一头牛向左移动任意多个位置（不能向右移动）。

求最少需要多少次操作才能将排列 a 变成排列 b。

算法思路

贪心策略：从左到右匹配目标排列，统计需要移动的牛的数量。

核心思想： - 使用两个指针 i 和 j 分别遍历目标排列 b 和当前排列 a - 使用 moved 数组记录已经被移动过的牛 - 对于目标排列的每个位置 i： - 找到下一个未被移动且等于 b[i] 的牛的位置 j - 如果 j 就是当前位置，说明这头牛不需要移动 - 否则，说明这头牛需要从后面移动过来，计数 +1，并标记为已移动

具体实现： - 初始化 j = 0，表示从左开始查找 - 对于每个目标位置 i： - 移动 j 直到找到未被移动的牛 - 如果这头牛正好是目标牛，指针后移 - 否则，这头牛需要移动到位置 i，计数 +1，标记为已移动

正确性证明

贪心选择性质：对于目标位置的每头牛 b[i]，如果当前未移动的牛中第一头正好是 b[i]，则不需要移动；否则，这头牛必须从后面移动过来，且这是唯一的选择（因为只能向左移动）。

最优性：每头需要移动的牛都必须至少被操作一次，因此最少操作数不可能小于需要移动的牛的数量。贪心策略正好达到这个下界，所以是最优的。

代码实现

n = int(input())
arr = [int(x) for x in input().split()]
target = [int(x) for x in input().split()]
moved = [False] * (n + 1)
ans = 0
j = 0
for i in range(n):
    while j < n and moved[arr[j]]:
        j += 1
    if j >= n:
        break
    if target[i] == arr[j]:
        j += 1
    else:
        ans += 1
        moved[target[i]] = True

print(ans)

时间复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

核心要点

1. 只能向左移动牛，所以从前向后匹配是最优的
2. 使用 moved 数组避免重复计算已经移动过的牛
3. 指针 j 只会向前移动，整体 O(n) 复杂度