关于网站优化的文章,浙江大洋建设集团有限公司网站,wordpress主题怎么写,分销商城源码php题目传送门#xff1a;
P3029 [USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前言#xff1a;
这道题的核心问题是在一条直线上分布着不同品种的牛#xff0c;要找出一个连续区间#xff0c;使得这个区间内包含所有不同品种的牛#xff0c;…题目传送门
P3029 [USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前言
这道题的核心问题是在一条直线上分布着不同品种的牛要找出一个连续区间使得这个区间内包含所有不同品种的牛并且这个区间的成本即区间内牛的最大和最小 x 坐标之差最小。整体来说是非常的简单易手。
#思路概括 我们将采用滑动窗口算法来解决这个问题。滑动窗口算法是一种在数组或序列上通过维护两个指针通常称为左指针和右指针来动态调整窗口大小从而解决各种子区间相关问题的有效方法。在本题中我们会利用这个算法不断尝试不同的连续区间找出满足条件的最小成本区间。
##实现具体步骤 1、数据读取与品种的统计 1.1、首先我们读取输入的牛的数量 N。 1.2、接着使用一个循环读取每头牛的 x 坐标 和品种 ID 并将其存储在一个结果体数组当中。 1.3、同时我们使用一个哈希表来记录每个品种的出现情况。在遍历牛的信息时将每个品种添加剂道哈希表当中这样咱们就能统计出不同品种的总数。 2、排序操作 我们为了方便实用华东窗口算法我们需要按照牛的 x 坐标对所有牛进行排序。通过自定义比较函数可以确保牛按照 x 坐标从小到大的排列。排序的时间复杂度是 这也是整个算法得主要时间开销之一。 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)。
####代码
#includebits/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;vectorc o;unordered_mapint, 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;
}
