题目大意:有n个区间,当有m个区间有公共部分时,求m个区间长度的最大值与最小值之差的最小值。
思路:按区间的长度从小到大排序,可知连续的几个区间最优,则用两个指针指其头尾,线性扫描,再用线段树区间覆盖。
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 1000009
#define INF 2147483647
using namespace std;
int n,m,i,j,cnt,ans=INF,sum[N<<2],lazy[N<<2],b[N<<1];
struct node{ int l,r,len; } a[N];
bool cmp(const node &x,const node &y)
{
return x.len<y.len;
}
int find(int l,int r,int x)
{
if (l==r) return l;
int mid=l+r>>1;
if (x<=b[mid]) find(l,mid,x);
else find(mid+1,r,x);
}
void up_date(int k,int x)
{
sum[k]+=x,lazy[k]+=x;
}
void change(int cur,int L,int R,int l,int r,int val)
{
if (L==l && R==r) { up_date(cur,val); return; }
int mid=L+R>>1;
if (lazy[cur])
{
up_date(cur<<1,lazy[cur]);
up_date(cur<<1|1,lazy[cur]);
lazy[cur]=0;
}
if (r<=mid) change(cur<<1,L,mid,l,r,val);
else if (l>mid) change(cur<<1|1,mid+1,R,l,r,val);
else change(cur<<1,L,mid,l,mid,val),change(cur<<1|1,mid+1,R,mid+1,r,val);
sum[cur]=max(sum[cur<<1],sum[cur<<1|1]);
}
void solve()
{
for (i=1;i<=n;i++)
{
while (sum[1]<m)
{
if (j==n) return; j++;
change(1,1,cnt,a[j].l,a[j].r,1);
}
ans=min(ans,a[j].len-a[i].len);
change(1,1,cnt,a[i].l,a[i].r,-1);
}
}
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
b[++cnt]=a[i].l,b[++cnt]=a[i].r;
a[i].len=a[i].r-a[i].l;
}
sort(a+1,a+n+1,cmp),sort(b+1,b+cnt+1);
for (i=1;i<=n;i++) a[i].l=find(1,cnt,a[i].l),a[i].r=find(1,cnt,a[i].r);
solve(); printf("%d\n",ans<INF?ans:-1);
return 0;
}