题目描述
由于高传染性的牛传染病 COWVID-19 的爆发,Farmer John 非常担忧他的奶牛们的健康。
尽管他尽了最大努力使他的 N 头奶牛们践行“社交距离”,还是有许多奶牛不幸染上了疾病。
编号为 1…N 的奶牛们分别位于一条长直道路上的不同位置(相当于一维数轴),奶牛 i 位于位置 xi。
Farmer John 知道存在一个半径 R,任何与一头被感染的奶牛距离不超过 R 单位的奶牛也会被感染(然后会传染给与其距离 R 单位内的奶牛,以此类推)。
不幸的是,Farmer John 并不确切知道 R 的值。
他只知道他的哪些奶牛被感染了。
给定这个数据,求出起初感染疾病的奶牛的最小数量。
输入格式
输入的第一行包含 N。
以下 N 行每行用两个整数 x 和 s 描述一头奶牛,其中 x 为位置,s 为 0 表示健康的奶牛,1 表示染病的奶牛,并且所有可能因传播而染病的奶牛均已染病。
输出格式
输出在疾病开始传播之前已经得病的奶牛的最小数量。
数据范围
1≤N≤1000,
0≤x≤106
样例
输入样例:
6
7 1
1 1
15 1
3 1
10 0
6 1
输出样例:
3
样例解释
在这个例子中,我们知道 R<3,否则位于位置 7 的奶牛会传染给位于位置 10 的奶牛。
所以,至少 3 头奶牛初始时已被感染:位于位置 1 和 3 的两头奶牛中的一头,位于位置 6 和 7 的两头奶牛中的一头,以及位于位置 15 的奶牛。
算法1
(模拟) $O(n)$
时间复杂度
参考文献
python3 代码
def main():
n = int(input())
nums = []
for _ in range(n):
x, f = map(int, input().split())
nums.append((x, f))
nums.sort()
R = float('inf')
for i in range(n - 1):
if nums[i][1] != nums[i + 1][1]:
R = min(R, nums[i + 1][0] - nums[i][0] - 1)
res = 0
i = 0
while i < n:
if nums[i][1] == 1:
res += 1
while i + 1 < n and nums[i + 1][0] - nums[i][0] <= R:
i += 1
i += 1
print(res)
if __name__ == "__main__":
main()
C++ 代码
#include <iostream>
#include <string.h>
#include <algorithm>
#include <limits.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
vector<pair<int, int>> nums;
for (int i = 0; i < n; i ++)
{
int x; cin >> x;
int f; cin >> f;
nums.push_back(pair<int, int>{x, f});
}
sort(nums.begin(), nums.end());
int R = INT_MAX;
for (int i = 0; i < n - 1; i ++)
{
if (nums[i].second != nums[i + 1].second)
{
R = min(R, nums[i + 1].first - nums[i].first - 1);
}
}
int res = 0;
int i = 0;
while (i < n)
{
if (nums[i].second == 1)
{
res ++;
while (i + 1 < n && nums[i + 1].first - nums[i].first <= R)
{
i ++;
}
}
i ++;
}
cout << res << endl;
return 0;
}
java 代码
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Node
{
int x;
int f;
Node() {}
Node(int x_, int f_)
{
x = x_;
f = f_;
}
}
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
List<Node> nums = new ArrayList<>();
for (int i = 0; i < n; i ++)
{
int x = scan.nextInt();
int f = scan.nextInt();
nums.add(new Node(x, f));
}
Collections.sort(nums, (o1, o2) -> o1.x - o2.x);
int R = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; i ++)
{
if (nums.get(i).f != nums.get(i + 1).f)
{
R = Math.min(R, nums.get(i + 1).x - nums.get(i).x - 1);
}
}
int res = 0;
int i = 0;
while (i < n)
{
//------- 找到一个发病源
if (nums.get(i).f == 1)
{
res ++;
//------- 他会往右传播
while (i + 1 < n && nums.get(i + 1).x - nums.get(i).x <= R)
{
i ++;
}
}
i ++;
}
System.out.println(res);
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
Collections.sort(nums, (o1, o2) -> o1.x - o2.x);这个写法是咋来的?有没有好的文章求推荐
%%%(刚学java)