P6907: 社交距离
传统题
1.000s
时间限制
256MB
内存限制
2 提交
1 解决
【题目描述】
【题目描述】
由于高传染性的牛传染病 COWVID-19
的爆发，Farmer John 非常担忧他的奶牛们的健康。
为了限制疾病的传播，Farmer John
的 N 头奶牛（2≤N≤10^5
）决定践行“社交距离”，分散到农场的各处。农场的形状如一维数轴，上有 M 个互不相交的区间（1≤M≤10^5
），其中有可用来放牧的青草。奶牛们想要使她们位于不同的整数位置，每个位置上均有草，并且最大化 D
的值，其中 D 为最近的两头奶牛之间的距离。请帮助奶牛们求出 D 的最大可能值。
【
输入格式】
（文件名：socdist.in
）：
输入的第一行包含 N
和 M。以下 M
行每行用两个整数 a 和 b 描述一个区间，其中 0≤a≤b≤10^18
。没有两个区间有重合部分或在端点处相交。位于一个区间的端点上的奶牛视为在草上。
【
输出格式】
（文件名：socdist.out
）：
输出 D
的最大可能值，使得所有奶牛之间的距离均不小于 D 单位。保证存在 D>0 的解。
【
输入样例】
：
5 3
0 2
4 7
9 9
【
输出样例】
：
2
【样例说明】
取到 D=2
的一种方式是令奶牛们处在位置 0、2
、4
、6
和 9。
【
测试点性质】
：
测试点 2-3
满足 b≤10^5
。
测试点 4-10
没有额外限制。