洛谷网站： P3029 [USACO11NOV] Cow Lineup S 题解

题目传送门：

P3029 [USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前言：

这道题的核心问题是在一条直线上分布着不同品种的牛，要找出一个连续区间，使得这个区间内包含所有不同品种的牛，并且这个区间的成本（即区间内牛的最大和最小 x 坐标之差）最小。整体来说是非常的简单易手。

#思路概括：

我们将采用滑动窗口算法来解决这个问题。滑动窗口算法是一种在数组或序列上通过维护两个指针（通常称为左指针和右指针）来动态调整窗口大小，从而解决各种子区间相关问题的有效方法。在本题中，我们会利用这个算法不断尝试不同的连续区间，找出满足条件的最小成本区间。

##实现具体步骤：

1、数据读取与品种的统计：

1.1、首先，我们读取输入的牛的数量 N。

1.2、接着，使用一个循环读取每头牛的 x 坐标和品种 ID ，并将其存储在一个结果体数组当中。

1.3、同时，我们使用一个哈希表，来记录每个品种的出现情况。在遍历牛的信息时，将每个品种添加剂道哈希表当中，这样咱们就能统计出不同品种的总数。

2、排序操作：

我们为了方便实用华东窗口算法，我们需要按照牛的 x 坐标对所有牛进行排序。通过自定义比较函数，可以确保牛按照 x 坐标从小到大的排列。排序的时间复杂度是 $o(n log n)$ ，这也是整个算法得主要时间开销之一。

3、滑动窗口初始化：

1.1、初始化两个指针 left 和 right 都指向这排序后数组的第一个元素，它们分别代表着滑动窗口的左右边界。

1.2、初始化cb为0，这用于记录当前窗口内不同品种的数量；初始化 m 为 INT_MAX，用于存储满足条件的最小成本。

4、滑动窗口操作：

1.1、扩大窗口：

不多移动 right 指针，将新的牛加入道窗口当中。

检查新加入的牛的品种在当前窗口内的数量，如果该品种之前在窗口内的数量为0，说明这是一个新的品种，将 cb 加上1。

同时更新该品种在窗口内的数量。

5、缩小窗口：

当 right 指针遍历完所有牛后，m 中存储的就是满足条件的最小成本，将其输出即可。

###复杂度分析：

1、时间复杂度：

排序操作的时间复杂度为 O(n log n)，滑动遍历数组的时间复杂度为 O(n），因此总的时间复杂度是 O(n log n)。

2、空间复杂度：

主要的空间开销在于存储牛的信息和哈希表，哈希值最多存储 k 个不同的品种，因此空间复杂度为 O(k)。

####代码：

#include<bits/stdc++.h>
using namespace std;
struct c {int x;int r;c(int x, int r) : x(x), r(r) {}
};
// 自定义比较函数，按照 x 坐标对牛进行排序
bool C(const c& a, const c& b) {return a.x < b.x;
}
int main() {int n;cin >> n;vector<c> o;unordered_map<int, int> bc;// 读取输入并存储牛的信息for (int i = 0; i < n; ++i) {int x, r;cin >> x >> r;o.emplace_back(x, r);bc[r] = 0;}// 统计不同品种的数量int u = bc.size();// 按照 x 坐标对牛进行排序sort(o.begin(), o.end(), C);int l = 0, r = 0;int cb = 0;int m = INT_MAX;// 滑动窗口while (r < n) {// 扩大窗口if (bc[o[r].r] == 0) {++cb;}++bc[o[r].r];// 当窗口内包含了所有不同品种的牛时，尝试缩小窗口while (cb == u) {m = min(m, o[r].x - o[l].x);--bc[o[l].r];if (bc[o[l].r] == 0) {--cb;}++l;}++r;}cout << m << endl;return 0;
}