按坐标排序奶牛，用 Counter 和双指针维护包含全部品种的最短坐标窗口。
OJ: luogu
题目 ID: P3029
难度:普及/提高-
标签:双指针滑动窗口计数python
日期: 2026-07-16 17:48
题意
在数轴上选择一个最短区间，使其中至少包含全体奶牛中每一种品种。
思路
先按坐标排序。右指针逐个加入奶牛；窗口已经包含全部品种时，不断移动左指针并更新长度，直到刚好缺少一种品种。
Python 知识
Counter保存窗口内各品种次数，删除计数归零的键后，len(counts)就是当前品种数。- 集合推导式
{breed for _, breed in cows}统计全局不同品种。 - 元组排序同时保留坐标和品种信息，参见
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md。
代码
python
from functools import partial
import sys
from itertools import batched
from collections import Counter
from bisect import bisect_left, bisect_right
data = list(map(int,sys.stdin.buffer.read().split()))
n = data[0]
cnt = Counter()
ans = 2 ** 30
def flow(value, *steps):
for step in steps:
value = step(value)
return value
# cows = list(batched(data[1:],2))
# cows.sort(key=lambda x: x[0])
cows = flow(
batched(data[1:],2),
list,
partial(sorted,key= lambda x : x[0])
)
# 离散化
dif = flow(
{id for _ , id in cows},
list,
sorted,
)
nid = lambda id: bisect_left(dif,id)
cows_difed = [(h,nid(id)) for h,id in cows]
# 不同的品种的奶牛的数量
required = len(dif)
# print(dif)
# print(cows_difed)
# 双指针
left = 0
for right in range(len(cows_difed)):
(pos,id) = cows_difed[right]
cnt[id] += 1
while len(cnt) == required:
ans = min(ans,pos - cows_difed[left][0])
lid = cows_difed[left][1]
cnt[lid] -= 1
if not cnt[lid]:
del cnt[lid]
left+=1
print(ans)复杂度
时间复杂度
总结
“最短区间覆盖全部类别”是排序后滑动窗口的典型模型。