USACO20 Open Bronze 9072 - Social Distancing II - C++ 解题思路与代码

{/u0022title/u0022: /u0022USACO20 Open Bronze 9072 - Social Distancing II - C++ 解题思路与代码/u0022, /u0022description/u0022: /u0022本篇文章详细介绍了 USACO20 Open Bronze 9072 - Social Distancing II 的解题思路与 C++ 代码实现，并提供了代码的复杂度分析。/u0022, /u0022keywords/u0022: /u0022USACO, Open Bronze, Social Distancing II, C++, 解题思路, 代码实现, 复杂度分析, 算法/u0022, /u0022content/u0022: /u0022## USACO20 Open Bronze 9072 - Social Distancing II/n/n题目描述:/n由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。/n/n尽管他尽了最大努力使他的 N 头奶牛们（1 ≤ N ≤ 1000）践行/u0022社交距离/u0022，还是有许多奶牛不幸染上了疾病。编号为 1…N 的奶牛们分别位于一条长直道路上的不同位置（相当于一维数轴），奶牛 i 位于位置 x i 。Farmer John 知道存在一个半径 R，任何与一头被感染的奶牛距离不超过 R 单位的奶牛也会被感染（然后会传染给与其距离 R 单位内的奶牛，以此类推）。/n/n不幸的是，Farmer John 并不确切知道 R 的值。他只知道他的哪些奶牛被感染了。给定这个数据，求出起初感染疾病的奶牛的最小数量。/n/n输入格式:/n输入的第一行包含 N。以下 N 行每行用两个整数 x 和 s 描述一头奶牛，其中 x 为位置（0 ≤ x ≤ 10^6），s 为 0 表示健康的奶牛，1 表示染病的奶牛，并且所有可能因传播而染病的奶牛均已染病。/n/n输出格式:/n输出在疾病开始传播之前已经得病的奶牛的最小数量。/n/n输入输出样例:/n样例 1/n输入样例 复制/n6/n7 1/n1 1/n15 1/n3 1/n10 0/n6 1/n输出样例 复制/n3/n/n样例说明:/n在这个例子中，我们知道 R<3，否则位于位置 7 的奶牛会传染给位于位置 10 的奶牛。所以，至少 3 头奶牛初始时已被感染：位于位置 1 和 3 的两头奶牛中的一头，位于位置 6 和 7 的两头奶牛中的一头，以及位于位置 15 的奶牛。/n/n## 解题思路/n1. 首先，将所有被感染的奶牛的位置坐标存储在一个数组中。/n2. 对这个数组进行排序，以便后面计算相邻奶牛之间的距离。/n3. 初始化最小感染数量为数组的长度。/n4. 遍历排序后的数组，计算相邻奶牛之间的距离，如果距离小于某个半径，则更新最小感染数量。/n5. 输出最小感染数量。/n/n## C++代码实现/ncpp/n#include <iostream>/n#include <vector>/n#include <algorithm>/nusing namespace std;/n/nint main() {/n int N;/n cin >> N;/n/n vector<int> infected;/n for (int i = 0; i < N; i++) {/n int x, s;/n cin >> x >> s;/n if (s == 1) {/n infected.push_back(x);/n }/n }/n/n sort(infected.begin(), infected.end());/n/n int minInfected = N;/n for (int i = 1; i < infected.size(); i++) {/n int distance = infected[i] - infected[i-1];/n if (distance < minInfected) {/n minInfected = distance;/n }/n }/n/n cout << minInfected << endl;/n/n return 0;/n}/n/n/n## 复杂度分析/n排序的时间复杂度为O(NlogN)，遍历排序后的数组的时间复杂度为O(N)，因此总的时间复杂度为O(NlogN)。空间复杂度为O(N)，用于存储被感染奶牛的位置坐标。/n/n希望这篇文章对您有所帮助。如果您有任何问题，请随时在评论区留言。/u002