题目名称	3389. [USACO20 Open Silver]Social Distancing
输入输出	`usaco_20Open_socdist.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	数声风笛ovo 于2020-04-04加入
开放分组	全部用户
提交状态
分类标签
	分享题解

关于 Social Distancing 的近10条评论(全部评论)
经过测试，数据无误，希望某些打表A题的人可以仔细思考自己代码的问题。数声风笛ovo 2020-04-04 23:41 1楼

3389. [USACO20 Open Silver]Social Distancing

★☆ 输入文件：usaco_20Open_socdist.in 输出文件：usaco_20Open_socdist.out 简单对比
时间限制：1 s 内存限制：256 MiB

由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。

为了限制疾病的传播，Farmer John 的 $N$ 头奶牛（$2 \leq N \leq 10^5$）决定践行“社交距离”，分散到农场的各处。

农场的形状如一维数轴，上有 $M$ 个互不相交的区间（$1 \leq M \leq 10^5$），其中有可用来放牧的青草。

奶牛们想要使她们位于不同的整数位置，每个位置上均有草，并且最大化 $D$ 的值，其中 $D$ 为最近的两头奶牛之间的距离。请帮助奶牛们求出 $D$ 的最大可能值。

输入的第一行包含 $N$ 和 $M$。

以下 $M$ 行每行用两个整数 $a$ 和 $b$ 描述一个区间，其中 $0 \leq a \leq b \leq 10^{18}$。没有两个区间有重合部分或在端点处相交。位于一个区间的端点上的奶牛视为在草上。

输出 $D$ 的最大可能值，使得所有奶牛之间的距离均不小于 $D$ 单位。

保证存在 $D>0$ 的解。

取到 $D=2$ 的一种方式是令奶牛们处在位置 $0$、$2$、$4$、$6$ 和 $9$。

对于$ 30\% $的测试数据(测试点$ 1 \sim 3 $)，满足$ b \le 10^5 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

USACO 美国公开赛 Silver 组