题解 P6281 【[USACO20OPEN]Social Distancing S】
kradcigam
2020-04-05 19:59:44
这道题是一个二分的模板，先讲一下二分。
二分是确定一个答案然后对其分析，而答案常常有这样一种情况：
或
题目通常会让我们找符合条件的最大值或最小值。
以这道题为例，就是要在可行的社交距离中找到最大值。
我们发现，社交距离比最优解大的都可以，不最优解小的都不可以。
这个我们叫左闭右开。
二分顾名思义，就是二分。
```cpp
int l=0,r=INT_MAX/2;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid))l=mid;//这里不同
else r=mid;//这里不同
}
```
我们可以去写一下 `check`:
```cpp
bool check(ll x){
ll l=0,ans=0;
for(int i=1;i<=m;i++){
l=max(l,a[i].a);//左端点
if(a[i].b>=l){//a[i].r是右端点
ll X=(a[i].b-l)/x+1;//站的牛的数量
ans=ans+X;//奶牛数量+X
l=l+X*x;//更新左端点
}
}
return ans>=n;//是否可行
}
```
总代码：
```cpp
#include <bits/stdc++.h>
#define int long long//注意开long long
using namespace std;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
const int MAXM=1e5+10;
struct node{
int a,b;
}a[MAXM];
int n,m;
bool check(int x){
int l=0,ans=0;
for(int i=1;i<=m;i++){
l=max(l,a[i].a);
if(a[i].b>=l){
int X=(a[i].b-l)/x+1;
ans=ans+X;
l=l+X*x;
}
}
return ans>=n;
}
bool cmp(node a,node b){
return a.a<b.a;
}
signed main(){
read(n);read(m);
for(int i=1;i<=m;i++)read(a[i].a),read(a[i].b);
sort(a+1,a+m+1,cmp);//排序
int l=1,r=INT_MAX;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid))l=mid;
else r=mid;
}cout<<l;
return 0;
}
```