题解 P6281 【[USACO20OPEN] Social Distancing S】
wylt
·
·
题解
USACO 2020 US Open 白银组T1 Social Distancing
原题面（英文）：http://www.usaco.org/index.php?page=viewproblem2&cpid=1038
官方题解（英文）：http://www.usaco.org/current/data/sol_socdist_silver_open20.html
题意简述
有 N 头奶牛，M 个互不相交的区间，奶牛只能在区间中且奶牛之间的最小间隔为 D，你需要最大化 D 。
题目分析
要求最大化最小值，很快可以看出是道二分答案的模板题。
那我们思路就是：
①因为题目未保证输入区间有序，以防万一先排个序，由于互不相交，只要给 a_{i} 排序就行了。
②用标准的二分模板，计算当前的 mid 并用 check 函数检验当 D=mid 时是否有解。
③在 check 函数中分别记录当前已经安放好的奶牛数和上一头奶牛的位置，有个优化是可以直接计算一段草地能够安放的奶牛数
cnt=ceil((float)(g[i].r-g[i].l+1)/D)
④既然我们可以快速求出一个区间内最多安放的奶牛数，则只要通过前一个区间最后一个奶牛的位置加 $D$ 就可以求出这个区间第一个可安放奶牛的位置。只要把 $g[i].l$ 替换为 $next+D$ 即可算出当前区间的最多安放奶牛数。
注意当 $next+D\le g[i].l$ 时不用替换。
⑤以此类推若此时已安放奶牛数大于 $N$ 就代表此时 $mid$ 可选，返回 $true$ 即可。
⑥回到主函数中，若返回 $true$ ，则 $l=mid+1$，否则 $r=mid-1$ 。
⑦当 $l>r$ 时，输出答案。
------------
### 代码
```cpp
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
using namespace std;
int n,m;
struct node{
long long l,r;
}g[100005];
bool cmp(node i,node j){
return i.l<j.l;
}
bool check(long long d){
long long cnt=ceil((float)(g[1].r-g[1].l+1)/d);
long long next=g[1].l+d*(cnt-1);
if(cnt>=n){
return true;
}
for(int i=2;i<=m;i++){
if(next+d>g[i].l){
long long tcnt=ceil((float)(g[i].r-next-d+1)/d);
next=next+d+d*(tcnt-1);
cnt+=tcnt;
if(cnt>=n){
return true;
}
} else {
long long tcnt=ceil((float)(g[i].r-g[i].l+1)/d);
next=g[i].l+d*(tcnt-1);
cnt+=tcnt;
if(cnt>=n){
return true;
}
}
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>g[i].l>>g[i].r;
}
sort(g+1,g+m+1,cmp);
long long l=0,r=g[m].r,ans;
while(l<=r){
long long mid=(l+r)>>1;
if(check(mid)){
ans=mid;
l=mid+1;
} else {
r=mid-1;
}
}
cout<<ans;
return 0;
}
```