P8660 题解

· · 题解

P8660 题解

题目-P8660 [蓝桥杯 2017 国 A] 区间移位

题意

如果你没看懂题：

你可以位移这些遮阳伞，使得空地都可以被遮住而不被太阳照射到 需要使**移动最远**的那个遮阳伞**位移的距离最小**

主体思路：二分

涉及到最大值最小或是最小值最大的问题，一般都是通过二分答案来解决的。

我们简要地证明一下：

如果遮阳伞最大位移是 x 时，都不能遮住所有的空地，那么最大位移比 x 小的情况也不可能遮住所有空地；

如果遮阳伞最大位移是 x 时，可以遮住所有的空地了，那最大位移再大一点的情况（不一定要达到），也可以遮住所有空地。

故答案具有单调性，也有两段性，可以二分答案。

二分板子

int binarySearch(){
    int l,r,mid;
    l=0,r=maxr;
    while(l<r){
        mid=l+(r-l)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    return l;
}

这里是整数二分的板子，但是答案会有小数怎么办。

其实很容易想到，当答案出现小数时，要想使得最大值最小，小数部分必须是 0.5，因此我们可以将数据都 \times 2，最后得到结果时再 \div 2 就好了，这样我们就可以放心地用二分板子了。

贪心

接下来的问题就是，check() 函数要怎么写。

我们可以用 t 来表示当前情况下，空地被覆盖的最右端（为了方便，我们是从左向右覆盖的）。

于是，我们在每次增加一个区间的时候，使右端点 t 尽可能地右，这就是贪心的思路。那么我们该如何实现呢？

分类讨论，一个区间和 t 就有 3 种情况：

1.区间左端点 > t

这时候，我们要先判断该区间能否覆盖到点 t。

如果能在满足最大位移为 x 的情况下覆盖到点 t，那我们就将区间左端点移至 t，并更新 t。

如果不能，我们就不管它（记住这句话，后面要考）。

2.区间左端点 =t

这种情况非常简单，我们直接更新 t 为区间右端点即可。

3.区间左端点 < t

对于这种情况，如果想要把右端点尽可能地右，就得让区间位移尽可能地大。

但是这个大也有限度：不超过最大位移 x 和区间左端点不超过 t。

注意：如果区间右移后右端点仍未超过 t，那我们也不会采用它。代码中用 \max() 实现。

那我们就可以开始愉快地写代码 \cdots\cdots 了？

并不！

现在又有新的问题：如何排列所有区间？

排列区间

方案 1：按左端点排序

也许你会觉得左端点靠左的就先判断，其实一开始我也是这么想的

看一组数据：

输入

4
0 10
12 14
11 20
21 10000

这里我们当然是选择把区间 [12,14] 向左位移 2 个单位，把区间 [11,20] 向右位移 1 个单位，最小值是 2。

如果按照左端点排序，就会先把区间 [11,20] 向左位移 1 个单位，再把区间 [12,14] 向右位移 7 个单位，最小值是 7，出错了。

方案 2：按右端点排序

所以正解是按右端点排序。

可能有人 其实还是我 会想到 hack 数据，那我顺便也讲一下为什么按右端点排序可以解决刚刚按左端点排序出现的问题。

输入

4 
0 10
17 19
11 20
21 10000

看到这个数据第一眼，如果按右端点排序，会先处理区间 [17,19]，然而最优解应该是先把 [11,20] 左移 1 个单位，把 [17,19] 右移 2 个单位，难道这是 hack？

当最大位移 x=7 时，会先考虑区间 [17,19]，此时可行，进行二分。

二分之后 x=3.5（为了方便采用小数表示，实际程序中会按前文操作处理），这时，虽然区间 [17,19] 排序靠前，但我们不会考虑它，因为这个区间在最大位移为 3.5 时不能覆盖到 t（值为 10），即这个区间不满足能连续接上已覆盖的最右端这个条件。

因此我们会跳过它，直接考虑区间 [11,20]，此时又可行，还会继续二分！这也就是按右端点排序优于按左端点排序的原因！

愉快写代码

铺垫了这么多，终于到代码实现了，太爽了！

注意一些代码实现细节

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
int n;
//存储区间:
struct st{
    int l,r;
};
vector<st> D;
//优先按右端点排序: 
bool cmp(st x,st y){
    if(x.r!=y.r)return x.r<y.r;
    else return x.l<y.l;
}
//验证答案:
bool check(int x){
    int t=0;
    vector<st> d(D);//复制一份用以删除用过的区间
    while(true){
        bool flag=0;//找没找到
        for(int i=0;i<d.size();i++){
            if(d[i].l>t){//需要把区间左移
                if(d[i].l-x<=t){//可以左移 
                    flag=1;
                    t+=d[i].r-d[i].l;
                    d.erase(d.begin()+i);//删除
                    i--;//删除后i要退1
                    break; 
                }
            }else if(d[i].l==t){//区间左端点刚好是t点
                flag=1;
                t=d[i].r;
                d.erase(d.begin()+i);
                i--;
                break;
            }else{//区间已覆盖t点 
                flag=1;
                t=max(t,d[i].r+min(x,t-d[i].l));//让更新后的t点尽可能地右(但是受到最大位移和覆盖到点t的限制)
                d.erase(d.begin()+i);
                i--;
                break;
            }
        }
        if(flag==0||d.empty())break;//没找到或者找完了就跳出 
    }
    return t>=20000;
}
//二分板子 
int binarySearch(){
    int l,r,mid;
    l=0,r=2*maxn;
    while(l<r){
        mid=l+(r-l)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    return l;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1,dl,dr;i<=n;i++){
        cin>>dl>>dr;
        D.push_back({2*dl,2*dr});//小数优化 
    }
    sort(D.begin(),D.end(),cmp);
    cout<<binarySearch()/2.0;//前面小数优化，这里记得除回去 
}

愉快地 AC 了

感谢观看！！！