首页 > 代码库 > 洛谷P1712 区间
洛谷P1712 区间
题目描述
在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。
输入输出格式
输入格式：
第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n
接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。
N<=500000,M<=200000,0≤li≤ri≤10^9
输出格式：
只有一行，包含一个正整数，即最小花费。
输入输出样例
输入样例#1：
6 33 51 23 42 21 51 4
输出样例#1：
2
说明
贪心 扫描 线段树
把区间按长度从小到大排序，依次加入。用线段树维护数轴上被覆盖的次数最多是多少，当大于m时，更新答案，并删掉最早加入的区间。
正确性显然。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int mxn=500020; 8 int read(){ 9 int x=0,f=1;char ch=getchar();10 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}11 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}12 return x*f;13 }14 struct node{15 int l,r;16 int val,mk;17 }t[mxn<<3];18 int rot,sz=0;19 #define ls t[rt].l20 #define rs t[rt].r21 void pushup(int rt){22 t[rt].val=max(t[ls].val,t[rs].val);return;23 }24 void PD(int rt){25 if(t[rt].mk){26 if(!ls)ls=++sz;27 t[ls].val+=t[rt].mk;t[ls].mk+=t[rt].mk;28 if(!rs)rs=++sz;29 t[rs].val+=t[rt].mk;t[rs].mk+=t[rt].mk;30 t[rt].mk=0;31 }32 return;33 }34 void update(int L,int R,int v,int l,int r,int &rt){35 if(!rt)rt=++sz;36 if(L<=l && r<=R){37 t[rt].mk+=v; t[rt].val+=v; return;38 }39 PD(rt);40 int mid=(l+r)>>1;41 if(L<=mid)update(L,R,v,l,mid,ls);42 if(R>mid)update(L,R,v,mid+1,r,rs);43 pushup(rt);44 return;45 }46 struct line{47 int L,R;48 int len;49 bool operator < (const line &b)const{50 return len<b.len;51 }52 }a[mxn];53 int n,m,mx;54 void solve(){55 int i,j;int ans=0x3f3f3f3f;56 int hd=1;57 for(int i=1;i<=n;i++){58 update(a[i].L,a[i].R,1,0,mx,rot);59 while(hd<=i && t[rot].val>=m){60 // printf("hd:%d val:%d\n",hd,t[rot].val);61 ans=min(ans,a[i].len-a[hd].len);62 update(a[hd].L,a[hd].R,-1,0,mx,rot);63 ++hd;64 }65 // printf("i:%d hd:%d\n",i,hd);66 }67 if(ans==0x3f3f3f3f)ans=-1;68 printf("%d\n",ans);69 return;70 }71 int st[mxn<<1],top=0;72 int main(){73 int i,j;74 n=read();m=read();75 for(i=1;i<=n;i++){76 a[i].L=read();a[i].R=read();77 a[i].len=a[i].R-a[i].L+1;78 st[++top]=a[i].L;st[++top]=a[i].R;79 mx=(a[i].R>mx)?a[i].R:mx;80 }81 sort(st+1,st+top+1);82 top=unique(st+1,st+top+1)-st-1;83 for(i=1;i<=n;i++){84 a[i].L=lower_bound(st+1,st+top+1,a[i].L)-st;85 a[i].R=lower_bound(st+1,st+top+1,a[i].R)-st;86 }87 mx=top;88 sort(a+1,a+n+1);89 solve();90 return 0;91 }
洛谷P1712 区间
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。