首页 > 代码库 > bzoj 4653: [Noi2016]区间
bzoj 4653: [Noi2016]区间
4653: [Noi2016]区间
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
3 5
1 2
3 4
2 2
1 5
1 4
Sample Output
2
题解：
还是要考虑排序。
我们按长度排序，发现最后选出的线段在一段区间上，把区间上的线段一条一条加到线段树中，最大值肯定>=m
然后枚举左端点，发现最近的右端点不断递增，用指针就好了。
#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;const int N=500005;#define p1 (p<<1)#define p2 (p<<1|1)struct node{ int a,id;}p[N<<1];struct Node{ int l,r,len;}q[N];int n,m,i,k,ans,x,t[N<<3],add[N<<3],h[N<<1];inline void read(int&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}bool cmp(const node&x,const node&y){ return x.a<y.a;}bool Cmp(const Node&x,const Node&y){ return x.len<y.len;}void update(int l,int r,int x,int y,int z,int p){ if(x<=l&&r<=y) { add[p]+=z; return; } if(add[p]!=0) { add[p1]+=add[p]; add[p2]+=add[p]; add[p]=0; } int mid=(l+r)>>1; if(x<=mid) update(l,mid,x,y,z,p1); if(y>mid) update(mid+1,r,x,y,z,p2); t[p]=max(t[p1]+add[p1],t[p2]+add[p2]);}int main(){ read(n),read(m); for(i=1;i<=n*2;i++) p[i].id=i; for(i=1;i<=n;i++) read(p[i*2-1].a),read(p[i*2].a),q[i].len=p[i*2].a-p[i*2-1].a; sort(p+1,p+n*2+1,cmp); h[p[1].id]=1;k=1; for(i=2;i<=n*2;i++) { if(p[i].a!=p[i-1].a) k++; h[p[i].id]=k; } for(i=1;i<=n;i++) q[i].l=h[i*2-1],q[i].r=h[i*2]; sort(q+1,q+n+1,Cmp); ans=2e9; for(i=1;i<=n;i++) { while(x<n&&t[1]<m) { x++; update(1,k,q[x].l,q[x].r,1,1); } if(t[1]>=m) ans=min(ans,q[x].len-q[i].len); update(1,k,q[i].l,q[i].r,-1,1); } if(ans==2e9) cout<<"-1";else cout<<ans; return 0;}
bzoj 4653: [Noi2016]区间
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。