题目概述

有 $n$ 个区间，求取 $m$ 个区间使得交不为空时的最小 $max\{len\}-min\{len\}$ 。

解题报告

我不会做题啦……很显然区间越多交越小而且解也不会优，所以可以按照长度排序之后直接two-pointer，然后用线段树查询是否交为空。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=500000,maxt=maxn<<1;

int n,m,x[maxn+5],y[maxn+5],tem[maxt+5];pair<int,int> a[maxn+5];
int MAX[(maxt<<2)+5],tag[(maxt<<2)+5],ans;

inline int Find(int x,int L=1,int R=tem[0]){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        x<=tem[mid]?R=mid-1:L=mid+1;return L;
}
#define Len(a) (tem[a.sc]-tem[a.fr])
inline bool cmp(const pair<int,int> &a,const pair<int,int> &b) {return Len(a)<Len(b);}
inline void Pushdown(int p){
    int now=tag[p];tag[p]=0;if (!now) return;
    MAX[p<<1]+=now;tag[p<<1]+=now;MAX[p<<1|1]+=now;tag[p<<1|1]+=now;
}
void Update(int L,int R,int k,int l=1,int r=tem[0],int p=1){
    if (L==l&&r==R) {MAX[p]+=k;tag[p]+=k;return;}int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Update(L,R,k,l,mid,p<<1); else if (L>mid) Update(L,R,k,mid+1,r,p<<1|1);
    else Update(L,mid,k,l,mid,p<<1),Update(mid+1,R,k,mid+1,r,p<<1|1);MAX[p]=max(MAX[p<<1],MAX[p<<1|1]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(scanf("%d%d",&n,&m),1);i<=n;i++)
        scanf("%d%d",&x[i],&y[i]),tem[++tem[0]]=x[i],tem[++tem[0]]=y[i];
    sort(tem+1,tem+1+tem[0]);tem[0]=unique(tem+1,tem+1+tem[0])-tem-1;
    for (int i=1;i<=n;i++) a[i]=mp(Find(x[i]),Find(y[i]));sort(a+1,a+1+n,cmp);
    for (int i=1,p=(ans=2e9,0);i<=n;i++){
        while (p<n&&MAX[1]<m) p++,Update(a[p].fr,a[p].sc,1);
        if (MAX[1]>=m) ans=min(ans,Len(a[p])-Len(a[i]));Update(a[i].fr,a[i].sc,-1);
    }return ans<2e9?printf("%d\n",ans):puts("-1"),0;
}