題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P3029 [USACO11NOV] Cow Lineup S

Problem Statement

題目簡述

在數線上給定 N 頭奶牛，每頭有座標 xix_i 與顏色 cic_i。
求最短的區間長度 [L,R][L, R]，使得該區間涵蓋所有不同顏色的奶牛至少一頭。

Constraints

約束條件

  • 1≤N≤5⋅1041 \le N \le 5 \cdot 10^4
  • 1≤xi,ci≤1091 \le x_i, c_i \le 10^9

思路：滑動窗口（值域 → 離散化）

核心問題

給定數線上的點（座標）與顏色，找一個最短區間，涵蓋所有顏色的點至少一次。

初步想法：從「值域滑動窗口」開始

如果座標範圍很小（例如最大值不超過 10510^5），最直接的想法是：

  1. 建立一個陣列，長度等於座標最大值，記錄每個座標上的顏色集合（可能有多頭同座標的牛）
  2. 使用雙指標 L 與 R 在值域上滑動，維護一個計數器記錄當前窗口內各顏色的出現次數
  3. 當涵蓋顏色數等於總顏色數 kk 時，記錄長度 R - L，並嘗試收縮左邊界

這種做法的時間複雜度為 O(M+N)\mathcal{O}(M + N)，其中 MM 是座標最大值，NN 是顏色點的數量。當 MM 高達 10910^9 時完全不可行——這也是本題的限制所在。

優化：離散化後僅考慮「有牛的座標」

由於我們只關心有牛的座標，而牛的數量 N≤5×104N \le 5 \times 10^4，可以把所有有牛的座標取出排序，然後在排序後的座標列表上進行滑動窗口，而非在整個值域上移動。

關鍵洞察

區間長度只會在兩個有牛的座標之間變化。移到沒有牛的空白區域不會改變涵蓋的顏色集合，只會徒增長度，所以最優解一定以某個有牛的座標作為左右端點。

處理相同座標多頭牛

在同一個座標上可能有多頭不同顏色的牛。加入窗口時必須一次加入該座標的所有顏色，移除時也必須全部移除，因為窗口邊界只能落在座標位置上，不能切開同一座標內的不同牛。

複雜度分析

  • 時間複雜度：O(Nlog⁡N)\mathcal{O}(N \log N)
    • 根據坐標排序 NN 頭牛需要 O(Nlog⁡N)\mathcal{O}(N \log N) 時間，滑動窗口需要 O(N)\mathcal{O}(N) 時間。
  • 空間複雜度：O(N)\mathcal{O}(N)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from collections import defaultdict


def solve():
    n = int(input())
    cows = [tuple(map(int, input().split())) for _ in range(n)]

    k = len(set(col for _, col in cows))

    mapX = defaultdict(list)
    for x, col in cows:
        mapX[x].append(col)
    Xs = sorted(mapX.keys())

    ans = float("inf")
    cnt = defaultdict(int)
    left = 0
    for _, x in enumerate(Xs):
        for col in mapX[x]:
            cnt[col] += 1
        while len(cnt) == k:
            ans = min(ans, x - Xs[left])
            for col in mapX[Xs[left]]:
                cnt[col] -= 1
                if cnt[col] == 0:
                    del cnt[col]
            left += 1

    print(ans)


if __name__ == "__main__":
    solve()