A29209.[USACO011NOV]

最小奶牛摄影区间 题解
题目大意
给定 $$n$$ 头奶牛，每头奶牛有位置 $$x$$ 和品种编号 $$id$$。
你需要选择一段连续位置区间拍照，使得照片中包含所有品种的奶牛。
求满足条件的区间的最小长度（最大x - 最小x）。
解题思路
本题是经典的全覆盖最小区间模板题，采用 排序 + 滑动窗口（双指针） 解决。

1. 排序：照片区间是一维数轴上的连续区间，因此先将所有奶牛按坐标 $$x$$ 从小到大排序。
2. 统计总品种数：遍历一遍所有奶牛，得到一共有多少种不同奶牛。
3. 滑动窗口：

• 右指针 $$r$$ 不断向右扩展窗口，加入新奶牛，统计窗口内各品种数量、当前品种总数。
• 当窗口左端点的品种数量大于 1 时，说明左端点可以舍去，左指针不断右移收缩窗口，保证窗口是当前合法的最窄状态。
• 当窗口内品种总数 = 全局总品种数时，更新答案最小区间长度。
  算法复杂度
• 排序：$$O(n\log n)$$
• 双指针遍历：每个点最多进、出窗口一次 $$O(n)$$
• 总体复杂度：$$O(n\log n)$$，可以通过 $$n \le 7\times 10^4$$ 的数据。
  AC 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 70010;
struct cow{
    int x,id;
}a[MAXN];

map<int,int> mp;
int n,sum;
int ans = LLONG_MAX;

bool cmp(cow a,cow b){
    return a.x < b.x;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i].x >> a[i].id;
        if(!mp[a[i].id]) sum++;
        mp[a[i].id]++;
    }
    // 按位置排序
    sort(a + 1,a + n + 1,cmp);
    mp.clear();

    int l = 1,cnt = 0;
    // 滑动窗口
    for(int r = 1;r <= n;r++){
        if(!mp[a[r].id]) cnt++;
        mp[a[r].id]++;

        // 左端点可以删就删，保持窗口最小
        while(mp[a[l].id] > 1){
            mp[a[l].id]--;
            l++;
        }
        // 全覆盖，更新答案
        if(cnt == sum){
            ans = min(ans,a[r].x - a[l].x);
        }
    }
    cout << ans << endl;
    return 0;
}

核心细节解释

1. 为什么要排序？
   照片拍到的是数轴上一段连续位置，只有把奶牛按坐标排序后，双指针窗口才能代表“连续区间”。
2. 收缩窗口的 while 语句
   while(mp[a[l].id] > 1)
   含义：窗口最左侧的奶牛品种在窗口内还有多余的数量，删掉它不会缺失品种，可以尝试缩小区间使答案更优。
3. 答案更新条件
   cnt == sum
   窗口内已经包含全部品种，此时的区间是合法解，不断取最小即可。
   易错点总结

• ❌ 不能用当前右端点品种判断收缩，必须判断左端点
• ❌ 未排序直接双指针，完全错误
• ❌ 窗口下标混乱、r++/++r 混用导致区间长度计算错误
• ✅ 优化：不需要额外 win 数组，直接在原数组双指针即可