[BZOJ4653][NOI2016]区间贪心+线段树

2024-03-02 20:16:52

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

题解：

拿到这个题，应该都有一种贪心的冲动

但是贪心贪的好不好就决定了能不能过……

我们先拿一棵线段树来维护区间加和全局最大值操作，

添加线段转化为区间+1，当全局最大值>=m时，我们就找到了一组合法解：虽然我们不知道到底是谁，但全局最大值已经>=m，线段集合中对应的m条线段就是合法解

现在问题就变成了找谁是合法解。

把线段按照长度排序，那么我们按照顺序添加这些线段，如果找到一组最优解，就先把找到的线段集合中最大值看成选择的最后那条线段，最小值看成第一条线段，然后把最小值向右逼近，看能不能更优，这样O（n）扫一遍，同时一直记录合法解的最小值，就能找到最后的答案了！

代码见下：

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <map>

 using namespace std;

 const int N=,inf=0x7fffffff;

 map<int,int> mp;

 int stack[N<<],top,cnt,n,m;

 struct line{int l,r,len;}seg[N];

 inline bool mt(const line &a,const line &b){return a.len<b.len;}

 struct node

 {

     node *ch[];int maxn,mark;

     node(){ch[]=ch[]=NULL;mark=maxn=;}

     inline void update(){maxn=max(ch[]->maxn,ch[]->maxn)+mark;}

 }*null=new node(),*root=null;

 inline node* newnode()

 {

     node *o=new node();

     o->maxn=o->mark=;

     o->ch[]=o->ch[]=null;

     return o;

 }

 inline void add(node *&rt,int l,int r,int L,int R,int val)

 {

     if(rt==null)rt=newnode();

     if(L<=l&&r<=R){rt->maxn+=val,rt->mark+=val;return;}

     int mi=(l+r)>>;

     if(L<=mi)add(rt->ch[],l,mi,L,R,val);

     if(mi<R)add(rt->ch[],mi+,r,L,R,val);

     rt->update();

 }

 int main()

 {

     scanf("%d%d",&n,&m);int ans=inf;

     for(int i=;i<=n;i++)

     {

         scanf("%d%d",&seg[i].l,&seg[i].r);

         seg[i].len=seg[i].r-seg[i].l;

         stack[++top]=seg[i].l,stack[++top]=seg[i].r;

     }

     sort(stack+,stack+top+);stack[]=-inf;

     for(int i=;i<=top;i++)

         if(stack[i]!=stack[i-])mp[stack[i]]=++cnt;

     for(int i=;i<=n;i++)seg[i].l=mp[seg[i].l],seg[i].r=mp[seg[i].r];

     sort(seg+,seg+n+,mt);root=newnode();

     for(int i=,j=;i<=n;i++)

     {

         add(root,,cnt,seg[i].l,seg[i].r,);

         while(root->maxn>=m)

         {

             ans=min(ans,seg[i].len-seg[j].len);

             add(root,,cnt,seg[j].l,seg[j].r,-);

             j++;

         }

     }

     printf("%d\n",(ans==inf)?-:ans);

 }

码农公寓