本文主要是介绍【NOI2016】bzoj4653 区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
只有一行，包含一个正整数，即最小花费。
很显然看出一点，选择的区间一定是按长度排序后连续的一段。这样可以先按长度排序，然后线性扫描。
扫描的时候需要快速判断当前是否合法，因为每次都是区间修改和区间询问，考虑线段树维护，每个叶子结点的权值即为覆盖这个点的区间数量，每个点维护区间最大值。维护两个指针，当左指针右移时，右指针也一直右移直到当前状态合法，然后更新答案。
最后分析一种错误的做法，只维护一个指针，每次取长度为m的一段判断是否合法。因为长度相等的区间可能有很多，最优解不一定将长度相等的区间全部取到，这种做法没有考虑到跳着取的情况。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct inter
{int l,r,len;bool operator < (const inter & iii) const{return len<iii.len;}
}a[500010],i1,i2;
int ori_l[500010],ori_r[500010],ord[1000010],lson[5000010],rson[5000010],val[5000010],tag[5000010],n,m,mx,cnt=1;
void build(int p,int ll,int rr)
{if (ll==rr) return;int mid=(ll+rr)/2;lson[p]=++cnt;build(cnt,ll,mid);rson[p]=++cnt;build(cnt,mid+1,rr);
}
void down(int p)
{if (tag[p]){val[p]+=tag[p];tag[lson[p]]+=tag[p];tag[rson[p]]+=tag[p];tag[p]=0;}
}
void up(int p)
{down(p);down(lson[p]);down(rson[p]);val[p]=max(val[lson[p]],val[rson[p]]);
}
void mark(int p,int ll,int rr,int l,int r,int x)
{down(p);if (ll==l&&rr==r){tag[p]=x;return;}int mid=(ll+rr)/2;if (r<=mid)mark(lson[p],ll,mid,l,r,x);else{if (l>mid)mark(rson[p],mid+1,rr,l,r,x);else{mark(lson[p],ll,mid,l,mid,x);mark(rson[p],mid+1,rr,mid+1,r,x);}}up(p);
}
int main()
{int i,j,k,x,y,z,tot=0,ans=0x3f3f3f3f;scanf("%d%d",&n,&m);for (i=1;i<=n;i++){scanf("%d%d",&ori_l[i],&ori_r[i]);ord[++tot]=ori_l[i];ord[++tot]=ori_r[i];}sort(ord+1,ord+tot+1);mx=unique(ord+1,ord+tot+1)-ord-1;for (i=1;i<=n;i++){a[i].len=ori_r[i]-ori_l[i];a[i].l=lower_bound(ord+1,ord+mx+1,ori_l[i])-ord;a[i].r=lower_bound(ord+1,ord+mx+1,ori_r[i])-ord;}build(1,1,mx);sort(a+1,a+n+1);for (i=1,j=0;i<=n;i++){if (i>1)mark(1,1,mx,a[i-1].l,a[i-1].r,-1);down(1);while (val[1]<m&&j<n){j++;mark(1,1,mx,a[j].l,a[j].r,1);}if (val[1]>=m)ans=min(ans,a[j].len-a[i].len);}if (ans==0x3f3f3f3f) printf("-1\n");else printf("%d\n",ans);
}这篇关于【NOI2016】bzoj4653 区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
