首页 > 代码库 > [BZOJ]4653: [Noi2016]区间

[BZOJ]4653: [Noi2016]区间

Time Limit: 60 Sec  Memory Limit: 256 MB

Description

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

Input

  第一行包含两个正整数 n,m用空格隔开,意义如上文所述。保证 1≤m≤n 
  接下来 n行,每行表示一个区间,包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。
  N<=500000,M<=200000,0≤li≤ri≤10^9

Output

  只有一行,包含一个正整数,即最小花费。

Sample Input

  6 3
  3 5
  1 2
  3 4
  2 2
  1 5
  1 4

Sample Output

  2

Solution

  傻逼题我想了好久,感觉自己好菜
  把线段按长度排序,从小到大加入线段树,当有一个点被覆盖了m次时,说明我们找到了一个可行的解,再从小到大把线段删掉,直到被覆盖m次的那个点只被覆盖了小于m次,最后被删掉的那条线段就是覆盖这个点的最早的那条线段,即可统计答案,而被我们删掉的这些线段已经不可能再作为更优的解的一部分了,所以每条线段被加入和删除最多一次,复杂度O(nlogn)。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
    int x;char c;
    while((c=getchar())<0||c>9);
    for(x=c-0;(c=getchar())>=0&&c<=9;)x=x*10+c-0;
    return x;
}
#define MN 500000
#define L (k<<1)
#define R (k<<1|1)
#define INF 0x7FFFFFFF
struct seg{int l,r,x;}s[MN+5];
bool cmp(const seg&a,const seg&b){return a.x<b.x;}
int c[MN*2+5],cn;
struct node{int l,r,mx,mk;}t[MN*8+5];
inline void up(int k){t[k].mx=max(t[L].mx,t[R].mx);}
inline void mark(int k,int x){t[k].mx+=x;t[k].mk+=x;}
inline void down(int k){if(t[k].mk)mark(L,t[k].mk),mark(R,t[k].mk),t[k].mk=0;}
void build(int k,int l,int r)
{
    if((t[k].l=l)==(t[k].r=r))return;
    int mid=l+r>>1;
    build(L,l,mid);build(R,mid+1,r);
}
void add(int k,int l,int r,int x)
{
    if(t[k].l==l&&t[k].r==r){mark(k,x);return;}
    int mid=t[k].l+t[k].r>>1;down(k);
    if(r<=mid)add(L,l,r,x);
    else if(l>mid)add(R,l,r,x);
    else add(L,l,mid,x),add(R,mid+1,r,x);
    up(k);
}
int main()
{
    int n,m,i,j,ans=INF;
    n=read();m=read();
    for(i=1;i<=n;++i)c[++cn]=s[i].l=read(),c[++cn]=s[i].r=read(),s[i].x=s[i].r-s[i].l;
    sort(c+1,c+cn+1);
    for(i=2,j=1;i<=cn;++i)if(c[i]!=c[j])c[++j]=c[i];cn=j;
    for(i=1;i<=n;++i)s[i].l=lower_bound(c+1,c+cn+1,s[i].l)-c,
                     s[i].r=lower_bound(c+1,c+cn+1,s[i].r)-c;
    sort(s+1,s+n+1,cmp);
    build(1,1,cn);
    for(i=j=1;i<=n;++i)
    {
        add(1,s[i].l,s[i].r,1);
        if(t[1].mx==m)
        {
            for(;t[1].mx==m;++j)add(1,s[j].l,s[j].r,-1);
            ans=min(ans,s[i].x-s[j-1].x);
        }
    }
    printf("%d",ans<INF?ans:-1);
}

 

[BZOJ]4653: [Noi2016]区间