UmiQS' Blog
0%

[蓝桥杯][题解]区间移位

发表于 分类于 ， Valine：

1. 试题

问题描述

数轴上有n个闭区间D1,…,Dn。其中区间Di用一对整数[ai, bi]来描述，满足ai < bi。已知这些区间的长度之和至少有10000。所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖[0, 10000]——也就是说[0, 10000]这个区间内的每一个点都落于至少一个区间内。
你希望找一个移动方法，使得位移差最大的那个区间的位移量最小。
具体来说，假设你将Di移动到[ai+ci, bi+ci]这个位置。你希望使得$max_i|c_i|$最小。

输入格式

输入的第一行包含一个整数n，表示区间的数量。
接下来有n行，每行2个整数ai,bi，以一个空格分开，表示区间[ai, bi]。保证区间的长度之和至少是10000。

输出格式

输出一个数，表示答案。如果答案是整数，只输出整数部分。如果答案不是整数，输出时四舍五入保留一位小数。

样例输入1

2
10 5010
4980 9980

样例输出1

20

样例说明1

第一个区间往左移动10；第二个区间往右移动20。

样例输入2

4
0 4000
3000 5000
5001 8000
7000 10000

样例输出2

0.5

样例说明2

第2个区间往右移0.5；第3个区间往左移0.5即可。

数据规模和约定

对于30%的评测用例，1 ≤ n ≤ 10；
对于100%的评测用例，1 ≤ n ≤ 10000，0 ≤ ai < bi ≤ 10000。

2. 算法分析

“求最大值最小。”
很容易想到二分。
但是二分什么量，如何判断二分的结果可行？
根据题意，可以考虑直接二分平移量，二分出来的结果就是需要的答案。
那么怎么检查(Check the answer)？
在数轴上，设被覆盖的区间的最大坐标为pos，初始值为0。现在用给出的区间从左到右覆盖数轴。自然想到要尽量使数轴的原来的右边界靠右，因为在左边界可以将pos的值覆盖掉时（即可以覆盖掉[0,pos]的区间并将其延长至[0,pos+x]，x在之后详细的代码中确定），原本的右边界越大，需要向右平移的量就越少。
对于一个由二分确定的平移量mid，若最终pos在N处或在N的右边，则该mid符合条件。
现在还有一个问题，题干中提示了结果可能是小数，那么我们需要在实数域中二分答案吗？
答案是否定的。经过分析直感A，当答案为小数时，它只可能以.5结尾。

反证法：证明小数部分只能出现.5

设现在区间的最大位移量的最小值为为一个小数$delta(0<delta<0.5)$。由于需要区间全覆盖，则根据直觉必定还有一个区间需要移动$1-delta$来凑整.
此时$delta<1-delta$，与$delta$是最大值相矛盾。
$∴$不可能出现小数部分不为.5的情况。

算法流程

  1. 输入给出的区间，形成一个区间结合，将其按照右边界b为第一个关键字升序排序，以后选择。由于答案的小数部分只可能有.5，故将所有坐标放大2倍再插入集合。

  2. 起始L=0，R=N=20000，开始二分位移量。
    每次check，pos初始化为0。
    在区间集合中寻找可以在平移量mid许可的范围中覆盖掉当前pos的区间，优先选择b小的（具体我也没想清楚为什么选b小的）。在选择好了区间后将其做标记，我这里使用的是multiset，即允许重复元素的set。每次二分拷贝一个原来multiset作为临时的集合，区间被选择以后将临时集合中的该区间删除。
    multiset和set的优点：插入后自动排序，方便删除。

  3. 将二分后的结果除以2，得到答案。

时间复杂度

二分法的复杂度是$O(logN)$，在二分法中有枚举集合（$O(N)$）->multiset删除操作（$O(logN)$），则总的时间复杂度是$O(Nlog^2N)$。

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;

int N=20000;
typedef pair<int,int> Range;
multiset<Range> a;

double BSearch(int L,int R)
{
    int pos,len,mid;
    while(L<=R)
    {
        multiset<Range> tmp(a);//拷贝一个临时的集合
        mid=(L+R)>>1;
        pos=0;
        while(1)
        {
            multiset<Range>::iterator it;
            int flag=0;
                        //枚举区间，越早枚举到的区间b越小
            for(it=tmp.begin();it!=tmp.end();it++)
            {
                int tL=(*it).second,tR=(*it).first;
                if(tL-mid<=pos&&pos<=tR+mid)
                {
                    flag=1;
                    len=tR-tL;
                                        //更新pos的值，注意分两种情况
                    if(pos<=tL+mid) pos+=len;
                      else pos=tR+mid;
                    tmp.erase(it);//区间在选择以后需要删除掉
                    break;
                }
            }
            if(!flag||pos>=N) break;
                        //flag=0，没有合适的区间可选；pos>=N，可以实现全覆盖
        }
        if(pos<N) L=mid+1;
          else  R=mid-1;
        //注意当pos=N时不可直接返回mid*1.0/2.0，不要想当然 
    } 
    return L*1.0/2.0;
}

int main()
{
    int L,R,i,T;
    double ans;
    cin>>T;
    for(i=1;i<=T;i++)
    {
        cin>>L>>R;
        L<<=1; R<<=1;
        a.insert({R,L});
    }
    ans=BSearch(0,N);
    cout<<ans<<endl;
    return 0;
}

4. 小结

该题方向很明确（使用二分法），但是细节多，小陷阱多，值得仔细回味。

这里是参考链接