Description

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1.

解题报告:

难得一道做得出的NOI，首先发现那一个相交的点一定可以是区间的某个端点，所以可以离散左右端点，那么问题就简单了，然后仔细推敲，发现可以按区间长度排序，然后不就是尺取法了么?如果有一个点被覆盖的次数>=m我们就移动左指针，不然我们就一直往后走，对于覆盖次数>=m我们就维护线段树区间最大值，然后区间修改维护指针移动即可

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define RG register#define il inline#define iter iterator#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#define ls (node<<1)#define rs (node<<1|1)using namespace std;const int N=500005;int b[N<<1],num=0,n,m,tr[N<<4],mark[N<<4];struct node{ int l,r,val; bool operator <(const node &pr)const{return val
          
           se || r
           
            >1;pushdown(node); updata(l,mid,ls,sa,se,ad);updata(mid+1,r,rs,sa,se,ad); upd(node);}void work(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].l,&a[i].r),a[i].val=a[i].r-a[i].l; b[++num]=a[i].l;b[++num]=a[i].r; } sort(a+1,a+n+1);sort(b+1,b+num+1); int tot=unique(b+1,b+num+1)-b-1; for(int i=1;i<=n;i++){ a[i].l=lower_bound(b+1,b+tot+1,a[i].l)-b; a[i].r=lower_bound(b+1,b+tot+1,a[i].r)-b; } int l=1,ans=2e9; for(int i=1;i<=n;i++){ updata(1,tot,1,a[i].l,a[i].r,1); while(tr[1]>=m && l
            
             =m)ans=Min(ans,a[i].val-a[l].val); } if(ans!=2e9)printf("%d\n",ans); else puts("-1");}int main(){ work(); return 0;}