题解 P6281 【[USACO20OPEN]Social Distancing S】

· · 题解

博客阅读体验更佳

题目分析

本题用二分去做，我们二分 D 的值，然后再 \Theta(N+M) 贪心扫一遍，如果可以放得下就往大的找，否则往小的找。

我们二分的范围是从 0 到 \max b_i，因为最坏的情况是每头牛都紧紧挨着一起，最优的情况是一头牛在数轴原点，另一头牛在数轴的最大值处。

虽然数轴是无限长的，但是在本题中，小于 0 的部分对答案没有贡献，大于 \max b_i 的部分也对答案没有贡献，所以我们假设数轴是从 0 到 \max b_i 的。

二分的复杂度为 \Theta(\log(\max b_i))，判断是否满足条件的复杂度为 \Theta(N+M)。

代码实现

回顾一下二分的模板:

while(l<r)
{
    mid=(l+r)/2+1;
    if(check()) l=mid;
    else r=mid-1;
}

复杂度为 \Theta(\log(\max b_i)) 。

下面是 check 函数，因为要遍历每头牛和每一段草坪，所以复杂度为 \Theta(N+M)。

实现方法见注释：

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 
}

完整代码：

#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;//完结撒花
}