| by XianKa | No comments

蓝桥杯历届试题 区间移位

http://lx.lanqiao.cn/problem.page?gpid=T451

题意是给定n<=10000个区间,保证总长度大于等于10000,有重叠,让求最大移动的最小值是多少。

首先这个问法就很二分,但是check的方法不好想。

wjjj随便猜了个结论就猜对了(%%%)。二分后按照b排序,优先选b小的。

因为二分出mid后,对于任意一个区间,只能在[a-mid,b+mid]里移动。所以最开始假设没有覆盖,当前点k=0,从左到右选出可以覆盖的区间,尽量往右放进行覆盖,覆盖完以后k移动到本次覆盖区间的最右边。在多个区间都可以覆盖当前点k的时候,b小的肯定在向右移动的时候不是最优解,因为它无论如何都比比它b大的移动得多。最后如果找不到方案可以覆盖完整个区间就说明答案太小,否则答案可能太大。至于小数,可以证明只会有0.5出现,因为最开始的区间都是整数,如果有一个区间移动了1/3那么必然有一个区间需要移动2/3。肯定不是最优解。既然只有0.5那直接把区间长度扩大一倍,规定只能移动整数距离,最后答案half就可以了。

在查找b的时候不能暴力找,否则会炸掉,可以用二分来找,但是注意标记已经用过的区间,我直接用了multiset方便删除用过的区间,复杂度都是logN。总复杂度Nlog²N

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const double eps=1e-12;
const int N=20000;
vector<pii> ab;
int vis[10001];
multiset<pii> c2;
int line[10001]; 
int main()
{
    int n,a,b;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        a*=2;b*=2;
        c2.insert({b,a});
    }
    int l=0,r=N;
    while(r>l)
    {
        multiset<pii> c1(c2);
        int mid=(l+r)>>1;
        int now=0;
        while(1)
        {
            int flag=0;
            multiset<pii>::iterator it;
            for(it=c1.begin();it!=c1.end();it++)
            {
                pii tmp=*it;
                int tta=tmp.second,ttb=tmp.first;
                if(tta-mid <= now && ttb+mid >= now)
                {
                    flag=1;
                    int len=ttb-tta;
                    if(now<=tta+mid) now+=len;
                    else now=ttb+mid;
                    c1.erase(it);
                    break;
                }
            }
            if(!flag || now>=N) break;
        }
        if(now>=N) r=mid;
        else l=mid+1;
    }
    double ans=l*1.0/2.0;
    cout<<ans;
}

 

 

发表评论