题目描述：
由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。
尽管他尽了最大努力使他的 N 头奶牛们践行“社交距离”，还是有许多奶牛不幸染上了疾病。
编号为 $ 1 \cdots N $ 的奶牛们分别位于一条长直道路上的不同位置（相当于一维数轴），奶牛 $ i $ 位于位置 $ x_i $ 。
Farmer John 知道存在一个半径 R，任何与一头被感染的奶牛距离不超过 R 单位的奶牛也会被感染（然后会传染给与其距离 R 单位内的奶牛，以此类推）。
不幸的是，Farmer John 并不确切知道 R 的值。
他只知道他的哪些奶牛被感染了。
给定这个数据，求出起初感染疾病的奶牛的最小数量。
输入格式
输入的第一行包含 N。
以下 N 行每行用两个整数 x 和 s 描述一头奶牛，其中 x 为位置，s 为 0 表示健康的奶牛，1 表示染病的奶牛，并且所有可能因传播而染病的奶牛均已染病。
输出格式
输出在疾病开始传播之前已经得病的奶牛的最小数量。
数据范围
输入样例：
1
2
3
4
5
6
7
| 6
7 1
1 1
15 1
3 1
10 0
6 1
|
输出样例：
题解：
首先遍历一遍，找到最短的相邻距离。然后就需要找出有多少个符合的区间。使用 while 循环会比较方便。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
vector<PII> a;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1, x, y; i <= n; i++)
{
cin >> x >> y;
a.push_back({x, y});
}
sort(a.begin(), a.end());
int r = INF;
for (int i = 0; i < n - 1; i++)
{
if (a[i].second != a[i + 1].second)
{
r = min(r, a[i + 1].first - a[i].first);
}
}
int ans = 0;
bool flag = false;
for (int i = 0; i < n; i++)
{
if (a[i].second == 1)
{
int j = i;
while (j + 1 < n && a[j + 1].second == 1 && a[j + 1].first - a[j].first < r)
{
j++;
}
ans++;
i = j;
}
}
cout << ans << endl;
return 0;
}
|