【题目来源】
洛谷：[P3029 USACO11NOV] Cow Lineup S - 洛谷
【题目描述】
农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种，他喜欢他的照片包含每个品种的至少一头牛。
约翰的牛都站在一条沿线的不同地方， 每一头牛由一个整数位置 \(X_i\) 以及整数品种编号 \(ID_i\) 表示。
约翰想拍一张照片，这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当，这就意味着，在一系列照片中的最大和最小 \(X\) 坐标的差距决定了照片的成本。
请帮助约翰计算最小的照片成本，这些照片中有每个不同的品种的至少一头牛，没有两头牛愿意站在同一个地点的。
【输入】
第 \(1\) 行：牛的数量 \(N\)；
第 \(2..1+N\) 行：每行包含 2 个以空格分隔的正整数 \(X_i\) 和 \(ID_i\)；意义如题目描述；
【输出】
输出共一行，包含每个不同品种 \(ID\) 的照片的最低成本。
【输入样例】
6
25 7
26 1
15 1
22 3
20 1
30 1
【输出样例】
4
【解题思路】
【算法标签】
《洛谷 P3029 Cow Lineup》 #单调队列# #离散化# #队列# #双指针,two-pointer# #USACO# #2011#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 奶牛结构体，存储位置和品种
struct cow
{int pos, type;
} a[50005]; // 存储所有奶牛信息int n, m, head, x, ans = 2e9; // n: 奶牛数量, m: 品种数, head: 滑动窗口左边界// x: 当前窗口包含的品种数, ans: 最小覆盖区间长度
map<int, int> s; // 记录各品种在窗口中的出现次数// 比较函数：按位置升序排序
bool cmp(cow x, cow y)
{return x.pos < y.pos;
}int main()
{// 输入奶牛数量cin >> n;// 输入每头奶牛的位置和品种，并记录品种for (int i = 0; i < n; i++) {cin >> a[i].pos >> a[i].type;s[a[i].type] = 1; // 标记该品种存在}m = s.size(); // 计算不同品种的总数// 按位置排序奶牛sort(a, a + n, cmp);// 滑动窗口算法寻找最小覆盖区间for (int i = 0; i < n; i++) {s[a[i].type]++; // 当前品种计数增加// 如果该品种首次在窗口中出现两次，增加xif (s[a[i].type] == 2) {x++;}// 当窗口包含所有品种时，尝试收缩左边界while (x == m) {// 更新最小区间长度ans = min(a[i].pos - a[head].pos, ans);// 左边界移动，对应品种计数减少s[a[head].type]--;// 如果某个品种不再满足覆盖条件，减少xif (s[a[head].type] == 1) {x--;}head++; // 移动左边界}}// 输出结果cout << ans;return 0;
}
【运行结果】
6
25 7
26 1
15 1
22 3
20 1
30 1
4