题解

#include<bits/stdc++.h>
#define int long long//懒得区分了
using namespace std;
int n,m,l,r,mid;
int a[123456],b[123456];
bool check()
{
int cur=a[1],cnt=1;//分别表示上一次放奶牛的位置和目前在用哪一块草坪
for(int i=2;i<=n;i++)//遍历每头牛，因为1号牛一定要放在a[1]的位置，所以可以在预处理里面解决
{
if(cur+mid<=b[cnt]) cur+=mid;//如果这块草坪够放，就放在这块草坪上
else//否则
{
while(cnt<m&&cur+mid>b[cnt]) cnt++;//找到下一个放牛的草坪
if(cur+mid>b[cnt]) return 0;//如果不够放，那么直接return 0
if(cur+mid<=a[cnt]) cur=a[cnt];
else cur+=mid;//同第一个if语句，放置这头牛
}
}
return 1;//若能放下就return 1
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i]>>b[i];//读入
sort(a+1,a+m+1);
sort(b+1,b+m+1);//排好序，方便贪心
l=0;r=b[m];//确定边界
while(l<r)//二分
{
mid=(l+r)/2+1;
if(check()) l=mid;
else r=mid-1;
}
cout<<l;//输出
return 0;//完结撒花
}