其他

M1100.机器人流水线调整

greedy, https://sunnywhy.com/problem/1100

在一个流水线数轴上有个机器人，每个机器人的初始位置用整数数组中的元素表示。接下来会有一次调整指令，每个机器人必须选择向左或向右移动恰好个单位。

请编写函数 long long f(int* C, int N, int K)，计算所有可能的调整方案中，机器人调整后位置的最小可能跨度，即所有机器人中最大位置与最小位置的差值。

输入描述

1 <= N <= 150

-2 * 10e8 <= Ci <= 2 * 10e8

0 <= K <= 2* 10e8

样例1

输入

3
0 4 0
1

输出

样例2

输入

2
5 10
0

输出

python

def f(C, N, K):
    if N == 1:
        return 0  # 单机器人，跨度为0

    C.sort()
    ans = C[-1] - C[0]  # 初始跨度
    for i in range(N - 1):
        # 前 i 个向右(+K)，后 N-i 个向左(-K)
        high = max(C[i] + K, C[-1] - K)
        low = min(C[0] + K, C[i+1] - K)
        ans = min(ans, high - low)
    return ans

# 输入处理
n = int(input())
C = list(map(int, input().split()))
k = int(input())
print(f(C, n, k))

M10065.独特蘑菇

sliding window, https://sunnywhy.com/problem/10065

熊熊和他的朋友晴天在森林里发现了一排神奇的蘑菇，每朵蘑菇都有一个独特的颜色值。熊熊想知道，从这排蘑菇中选取一段连续的蘑菇，且这段蘑菇的颜色种类不超过种，这样的选取方式有多少种。

输入描述

第一行包含两个整数 n 和 k （1 ≤ k ≤ n ≤ 10^5），分别表示蘑菇的数量和允许的最大颜色种类数。

第二行包含 n 个整数 c1, c2, ..., cn （1 ≤ ci ≤ 10^9），表示每朵蘑菇的颜色值。

输出描述

输出一个整数，表示满足条件的选取方式的数量。

样例1

输入

5 2
1 2 1 3 4

输出

解释

满足条件的选取方式有：

单独选取每朵蘑菇（5 种）
选取连续的 2 朵蘑菇：1-2, 2-1, 1-3, 3-4（4 种）
选取连续的 3 朵蘑菇：1-2-1（1 种）

总共有 10 种满足条件的选取方式。

样例2

输入

6 3
1 2 1 2 3 4

输出

解释

满足条件的选取方式有：

单独选取每朵蘑菇（6 种）
选取连续的 2 朵蘑菇（5 种）
选取连续的 3 朵蘑菇（4 种）
选取连续的 4 朵蘑菇（2 种）
选取连续的 5 朵蘑菇（1 种）

总共有 18 种满足条件的选取方式。

这是一个经典的滑动窗口（Two Pointers / Sliding Window）问题。

核心思路

需要找到所有的连续子数组，使得子数组内的不同数字（颜色）个数不超过 $K$ 。

双指针维护窗口：
- 使用两个指针 left 和 right，分别表示当前连续区间的左右边界。
- right 指针主动向右移动，每次将新的蘑菇加入窗口。
- left 指针被动向右移动，当窗口内的颜色种类超过 $K$ 时，left 需要收缩，直到颜色种类回到 $K$ 或以下。
计算满足条件的子数组数量：
- 对于每一个固定的 right，如果区间 [left, right] 内的颜色种类 $\leq K$ ，那么以 right 为结尾、且满足条件的所有子数组都是合法的。
- 这些合法的子数组具体是：[right, right], [right-1, right], ..., [left, right]。
- 这个数量恰好是 right - left + 1。
- 我们将每次移动 right 后的这个增量累加起来，就是最终答案。
统计颜色种类：
- 使用一个哈希表（Python 中的 dict 或 collections.defaultdict）来记录当前窗口内每种颜色出现的次数。
- 一个计数器 distinct_count 记录当前有多少种不同的颜色（或者直接使用 len(window_dict)）。

Python 代码实现

python

import sys
from collections import defaultdict

def solve():
    # 读取所有输入数据
    input = sys.stdin.read
    data = input().split()
    
    if not data:
        return

    # 解析 N 和 K
    n = int(data[0])
    k = int(data[1])
    
    # 解析蘑菇颜色数组
    mushrooms = []
    idx = 2
    # 处理输入可能分多行的情况
    while idx < len(data):
        mushrooms.append(int(data[idx]))
        idx += 1
    
    # 颜色计数器
    color_counts = defaultdict(int)
    # 当前窗口内不同颜色的数量
    distinct_colors = 0
    
    left = 0
    total_ways = 0
    
    # 滑动窗口：right 从 0 到 n-1
    for right in range(n):
        # 1. 将当前 right 指向的蘑菇加入窗口
        color = mushrooms[right]
        if color_counts[color] == 0:
            distinct_colors += 1
        color_counts[color] += 1
        
        # 2. 如果不同颜色数量超过 K，移动 left 收缩窗口
        while distinct_colors > k:
            left_color = mushrooms[left]
            color_counts[left_color] -= 1
            if color_counts[left_color] == 0:
                distinct_colors -= 1
            left += 1
        
        # 3. 累加合法子数组数量
        # 以 right 结尾的合法子数组个数为 (right - left + 1)
        total_ways += (right - left + 1)
        
    print(total_ways)

if __name__ == "__main__":
    solve()

代码详解

输入处理：使用 sys.stdin.read().split() 一次性读取所有输入，这在处理大量数据时比 input() 更快且更稳健。
数据结构：color_counts 用来记录窗口里每种颜色出现了几次。
主要逻辑：
- right 每向右移一步，我们就把新进来的颜色计数加 1。如果是新出现的颜色（计数从0变1），distinct_colors 加 1。
- 检查 distinct_colors > k。如果超过了，就开始移动 left。每移出一个左边的颜色，计数减 1。如果某个颜色计数变回 0，说明这个颜色彻底从窗口消失了，distinct_colors 减 1。
- 每次循环结束时，窗口 [left, right] 是满足条件的最长区间。包含在其中的、以 right 结尾的所有子区间都满足条件，数量为 right - left + 1。

python

import sys

# 设置快速IO
input = sys.stdin.read

def solve():
    data = input().split()
    if not data:
        return
    
    # 解析 N 和 K
    n = int(data[0])
    k = int(data[1])
    
    # 剩下的数据是蘑菇颜色
    # 使用迭代器避免切片产生的内存开销
    iterator = iter(data)
    next(iterator) # 跳过 n
    next(iterator) # 跳过 k
    
    ans = 0
    point = 0
    
    # color_pos 充当 LRU 缓存
    # key: 颜色, value: 该颜色最后一次出现的下标
    # 字典的顺序就是颜色最后出现位置的先后顺序
    color_pos = {}
    
    # 模拟 enumerate，idx 是下标
    idx = 0
    for val_str in iterator:
        color = int(val_str)
        
        # 1. 如果颜色已存在，删除旧记录，以便稍后重新插入到字典末尾
        if color in color_pos:
            del color_pos[color]
        
        # 2. 记录当前颜色的最新下标（这会将它放到字典末尾）
        color_pos[color] = idx
        
        # 3. 如果颜色种类超过 K，移除“最老”的那个颜色
        if len(color_pos) > k:
            # 获取字典里最早插入的一个键（也就是最后出现位置最小的那个颜色）
            oldest_color = next(iter(color_pos))
            # 左指针跳跃到该颜色结束位置的下一位
            point = color_pos[oldest_color] + 1
            # 彻底移除该颜色
            del color_pos[oldest_color]
            
        # 4. 累加答案
        ans += idx - point + 1
        idx += 1
        
    print(ans)

if __name__ == "__main__":
    solve()

M51044.火星购物

https://sunnywhy.com/problem/51044

在火星上购物是一种非常不同的体验。火星人使用由钻石组成的链条来支付。每个钻石都有一个价值（以火星元 M为单位）。在支付时，链条可以在任意位置切割一次，并且可以依次取下一些钻石。一旦钻石被取下，就不能再放回链条。例如，如果我们有一个由颗钻石组成的链条，其价值分别为3, 2, 1, 5, 4, 6, 8, 7，并且我们需要支付 M$15。我们可能有以下三种选择：

在 4 和 6 之间切割链条，并取下位置 1 到 5 的钻石（价值为 3+2+1+5+4=15）。
在 5 之前或 6 之后切割链条，并取下位置 4 到 6 的钻石（价值为 5+4+6=15）。
在 8 之前切割链条，并取下位置 7 到 8 的钻石（价值为 8+7=15）。

现在给定钻石链条的价值和顾客需要支付的金额，你需要列出所有可能的支付方案。

如果无法精确支付所需金额，你必须提供损失最小的解决方案。

输入

第一行包含两个整数 N（1 ≤ N ≤ 10^5）和 M（1 ≤ M ≤ 10^8），分别表示链条上的钻石数量和顾客需要支付的金额。

第二行包含 N 个正整数 D1, D2, ..., DN（1 ≤ Di ≤ 10^3），表示每颗钻石的价值。所有数字之间用空格分隔。

输出

对于每个测试用例，如果存在精确支付方案，输出所有满足 Di + ... + Dj = M 的 i-j 对，每对占一行，按 i 的递增顺序输出。

如果不存在精确支付方案，输出所有满足 Di + ... + Dj > M 且 (Di + ... + Dj − M) 最小的 i-j 对，同样按 i 的递增顺序输出。

样例1

输入

5 13
2 4 5 7 9

输出

2-4
4-5

来源

PAT

可以使用滑动窗口（双指针）算法在 $O (N)$ 的时间复杂度内解决，这对于 $N = 10^{5}$ 的数据规模是必要的。

解题思路

核心逻辑：我们需要找到一个连续的钻石子序列，使其总价值 $S u m$ 满足以下条件：
- 如果存在 $S u m = M$ 的方案，则输出所有这样的方案。
- 如果不存在 $S u m = M$ 的方案，则输出所有 $S u m > M$ 且 $(S u m - M)$ 最小的方案。
滑动窗口：
- 使用两个指针 left 和 right 维护一个窗口 [left, right]，表示当前选中的钻石链条片段。
- 不断向右移动 right 指针，累加钻石价值到 current_sum。
- 当 current_sum >= M 时，说明当前片段已经足够支付（或者是潜在的最小损失方案）。此时：
  - 计算 diff = current_sum - M。
  - 如果 diff 比当前记录的最小损失 min_loss 更小，说明找到了更优解（更接近 M），清空之前的旧结果，更新 min_loss，并记录当前区间。
  - 如果 diff 等于 min_loss，则将当前区间追加到结果列表中。
  - 尝试从左侧收缩窗口（current_sum -= diamonds[left]，left += 1），看看能否在保持 $S u m \geq M$ 的前提下获得更小的 $S u m$ ，或者找到下一个可能的起点。
优先级：算法自然地处理了优先级问题。一旦找到精确匹配（diff == 0），min_loss 变为 0，后续只有同样精确匹配的方案会被加入，所有 diff > 0 的方案都会被忽略。

Python 代码

python

import sys

def solve():
    # 使用 sys.stdin.read 读取所有输入，以应对大量数据时的IO瓶颈
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return

    iterator = iter(input_data)
    
    try:
        # 读取 N (钻石数量) 和 M (目标金额)
        N = int(next(iterator))
        M = int(next(iterator))
    except StopIteration:
        return
        
    # 读取 N 个钻石的价值
    diamonds = [int(next(iterator)) for _ in range(N)]
    
    # 初始化滑动窗口变量
    left = 0
    current_sum = 0
    min_loss = float('inf') # 记录当前找到的最小损失 (Sum - M)
    results = [] # 存储结果 (start_index, end_index)
    
    # 开始滑动窗口
    for right in range(N):
        # 扩展窗口右边界
        current_sum += diamonds[right]
        
        # 当当前和大于等于 M 时，尝试更新结果并收缩左边界
        while current_sum >= M:
            diff = current_sum - M
            
            if diff < min_loss:
                # 发现了更接近 M 的方案（更小的损失）
                # 更新最小损失，并重置结果列表（之前的方案不再是最优）
                min_loss = diff
                results = [(left + 1, right + 1)]
            elif diff == min_loss:
                # 发现了与当前最优解损失相同的方案，追加到列表
                results.append((left + 1, right + 1))
            
            # 收缩窗口左边界，寻找更短或更靠右的可能解
            current_sum -= diamonds[left]
            left += 1
            
    # 输出结果
    # 题目要求按 i (起始位置) 递增顺序输出
    # 由于我们是按 right 递增遍历，且 left 也是单调递增的，results 中的顺序自然满足要求
    for start, end in results:
        print(f"{start}-{end}")

if __name__ == '__main__':
    solve()

其他 ​

M1100.机器人流水线调整 ​

M10065.独特蘑菇 ​

M51044.火星购物 ​

其他

M1100.机器人流水线调整

M10065.独特蘑菇

M51044.火星购物