题解 P6281 【[USACO20OPEN]Social Distancing S】

2020-04-05 19:59:44


这道题是一个二分的模板,先讲一下二分。

二分是确定一个答案然后对其分析,而答案常常有这样一种情况:

题目通常会让我们找符合条件的最大值或最小值。

以这道题为例,就是要在可行的社交距离中找到最大值。

我们发现,社交距离比最优解大的都可以,不最优解小的都不可以。

这个我们叫左闭右开。

二分顾名思义,就是二分。

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:

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;//是否可行
}

总代码:

#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;
}