[BZOJ4653/Luogu1712][NOI2016]区间(线段树,尺取法)

发布于 2018-04-17  55 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4653/Luogu1712][NOI2016]区间(线段树,尺取法)

Description

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间,使得这 m个区间共同包含至少一个位置。换句话说,就是使得存在一个 x,使得对于每一个被选中的区间 [li,ri],都有 li≤x≤ri。
对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li,即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案,输出 −1。

Tag

线段树,尺取法。

解决思路

由于题目定义方案的花费为最长区间的长度-最短区间长度,那么长度在两者之间的区间是都可以加进去的。所以如果爱把区间按照长度排序后,任意一个合法方案都是一段连续区间的组合。
那么,可以用尺取法维护这个合法区间。每一次加入一个区间,就在对应线段树节点进行区间加法操作,若全局max等于要求的m时,此时表示至少有一个位置被m个区间覆盖,记录答案,然后移动左端点去掉一个区间,继续做。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lson (now<<1)
#define rson (lson|1)

const int maxN=501000*2;
const int inf=2147483647;

class Range
{
public:
    int l,r,len;
};

class SegmentData
{
public:
    int mx,lazy;
};

int n,m;
Range R[maxN];
int numcnt,Num[maxN*2];
SegmentData S[maxN*4];

bool operator < (Range A,Range B);
void PushDown(int now);
void Modify(int now,int l,int r,int ql,int qr,int key);

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>R[i].l>>R[i].r;R[i].len=R[i].r-R[i].l;
        Num[++numcnt]=R[i].l;Num[++numcnt]=R[i].r;
    }
    //离散
    sort(&Num[1],&Num[numcnt+1]);
    numcnt=unique(&Num[1],&Num[numcnt+1])-Num-1;
    for (int i=1;i<=n;i++)
    {
        R[i].l=lower_bound(&Num[1],&Num[numcnt+1],R[i].l)-Num;
        R[i].r=lower_bound(&Num[1],&Num[numcnt+1],R[i].r)-Num;
    }
    sort(&R[1],&R[n+1]);//将区间按照长度排序
    int Ans=inf;
    for (int i=1,j=0;i<=n;i++)//尺取
    {
        while ((j<n)&&(S[1].mx<m))//移动右端点加入区间
        {
            j++;
            Modify(1,1,numcnt,R[j].l,R[j].r,1);
        }
        if (S[1].mx==m) Ans=min(Ans,R[j].len-R[i].len);//若最大值等于m,则记录最优答案
        else break;
        Modify(1,1,numcnt,R[i].l,R[i].r,-1);//删除左端点区间
    }
    if (Ans==inf) cout<<-1<<endl;
    else cout<<Ans<<endl;
    return 0;
}

bool operator < (Range A,Range B)
{
    return A.len<B.len;
}

void PushDown(int now)
{
    if (S[now].lazy)
    {
        int lz=S[now].lazy;
        S[lson].mx+=lz;S[lson].lazy+=lz;
        S[rson].mx+=lz;S[rson].lazy+=lz;
        S[now].lazy=0;
    }
    return;
}

void Modify(int now,int l,int r,int ql,int qr,int key)
{
    if ((l==ql)&&(r==qr))
    {
        S[now].mx+=key;S[now].lazy+=key;
        return;
    }
    PushDown(now);
    int mid=(l+r)>>1;
    if (qr<=mid) Modify(lson,l,mid,ql,qr,key);
    else if (ql>=mid+1) Modify(rson,mid+1,r,ql,qr,key);
    else
    {
        Modify(lson,l,mid,ql,mid,key);
        Modify(rson,mid+1,r,mid+1,qr,key);
    }
    S[now].mx=max(S[lson].mx,S[rson].mx);
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4653/Luogu1712][NOI2016]区间(线段树,尺取法)


HNCJ OIer 一枚