题目
分析
这题是典型的“滑动窗口”应用。
首先将所有的牛按照位置排序，题目保证不会有两头牛站在同一个位置：
struct Cow {
int x; //位置
int breed; //品种
};
...
{
sort(cows.begin(), cows.end(), [](const Cow&a, const Cow& b){return a.x<b.x})
}一个基本的思路是：从0开始不断向右加入一头牛，直到加入了所有品种的牛，然后不断增加左边界，直到发现品种不够了为止。这时可以扩展右边界，看看是否有更好的解。
以样本数据为例，经过排序后，牛的位置和品种如下：
位置 15 20 22 25 26 30
品种 1 1 3 7 1 1从0号位开始，不断向右扩展窗口，到3号位的时候，窗口中的牛品种是：1 1 3 7，用map表示更简单：1(2) 3(1) 7(1)。这时可以增加左边界，变成20-25，宽度是5。但这不一定是最优解，此时我们再扩充右边界，到20-26，同样包括所有品种，但20这个位置可以去掉（增加左边界）。最终可以是22-26，宽度是4，结果更优。
核心代码是：
for(int right = 0;right < n; i++)
{
windows_breed[cows.breed]++; //一头新牛进入窗口，更新该品种对应的数量。
while(windows_breeed.size() == total_breeds) //如果窗口内品种数和总品种数相同，可以扩大左边界
{
int cost = cows.x - cows.x;
min_cost = min(min_cost, cost); //更新最小窗口宽度
windows_breed[cows.breed]--;
if(windows_breed[cows.breed] == 0) //没有这个品种的奶牛了！
{
windows_breed.erase([cows.breed]); //在集合中拿走这个品种的关键词以更新品种数量
}
left++;
}
}答案
思考
用滑动窗口，算法复杂度降低为\(O(n logn)\)。
这个代码演示了“滑动窗口”的标准模版，贴出如下供大家参考：
// 滑动窗口通用模板
for (int right = 0; right < n; right++)
{
// 1. 扩展右边界，更新窗口状态
add_to_window(right);
// 2. 收缩左边界，寻找最优解
while (window_is_valid()) {
update_answer();
remove_from_window(left);
left++;
}
}