Social Distancing II

题目描述

由于高度传染性的牛类疾病 COWVID-19 爆发，Farmer John 很担心他的奶牛健康状况。 尽管他尽力让他的 $N$ 头奶牛（$1 \leq N \leq 1000$）进行“社交距离”，但其中许多仍不幸感染了疾病。 这些奶牛方便地编号为 $1 \ldots N$，每头奶牛都站在一条很长的道路上（本质上是一维数轴）互不相同的位置上，第 $i$ 头奶牛站在位置 $x_i$。Farmer John 知道存在一个半径 $R$，使得任何距离一头感染牛不超过（含）$R$ 个单位的奶牛也会被感染（并且随后会将感染传播给距离它不超过 $R$ 个单位的更多奶牛，依此类推）。 不幸的是，Farmer John 并不知道 $R$ 的确切值。但他确实知道哪些奶牛已经感染。给定这些数据，请确定最初可能感染的奶牛数量的最小值。

输入格式

第一行输入包含 $N$。 接下来的 $N$ 行每行用两个整数 $x$ 和 $s$ 描述一头奶牛，其中 $x$ 是位置（$0 \leq x \leq 10^6$），$s$ 为 0 表示健康奶牛，为 1 表示患病奶牛。 至少有一头奶牛患病，并且所有可能通过疾病传播而变病的奶牛现在都已经变病。

输出格式

请输出在疾病发生任何传播之前，最初可能患病的奶牛数量的最小值。

6
7 1
1 1
15 1
3 1
10 0
6 1

3

提示

在这个例子中，我们知道 $R < 3$，因为否则位置 7 的奶牛会感染位置 10 的奶牛。因此，至少有 3 头奶牛必须一开始就感染——位置 1 和 3 的两头奶牛中至少有一头、位置 6 和 7 的两头奶牛中至少有一头，以及位置 15 的奶牛。 题目来源：Brian Dean

标签: USACO|2020|Bronze

来源

USACO|2020|Bronze