首页 > 代码库 > [UOJ #222][NOI2016]区间（线段树）
[UOJ #222][NOI2016]区间（线段树）
Description
在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值
求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。
Solution
对区间的长度排序，离散化，然后线段树维护每个点被覆盖过的次数，根据决策的单调性就可做了
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#define MAXN 500005#define INF 0x3f3f3f3fusing namespace std;int n,m;int a[MAXN*2],cnt=0;int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;}struct Node1{ int L,R,len;}d[MAXN];bool cmp(Node1 x,Node1 y){ return x.len<y.len; }struct Node2{ int l,r,tag,maxn;}t[MAXN*8];void pushdown(int idx){ if(t[idx].tag&&t[idx].l!=t[idx].r) { int tag=t[idx].tag; t[idx].tag=0; t[idx<<1].tag+=tag; t[idx<<1|1].tag+=tag; t[idx<<1].maxn+=tag; t[idx<<1|1].maxn+=tag; }}void update(int idx){ t[idx].maxn=max(t[idx<<1].maxn,t[idx<<1|1].maxn);}void build(int idx,int l,int r){ t[idx].l=l,t[idx].r=r,t[idx].maxn=t[idx].tag=0; if(l==r)return; int mid=(l+r)>>1; build(idx<<1,l,mid); build(idx<<1|1,mid+1,r);}void add(int idx,int x,int y,int z){ if(x<=t[idx].l&&y>=t[idx].r) { t[idx].maxn+=z; t[idx].tag+=z; return; } pushdown(idx); int mid=(t[idx].l+t[idx].r)>>1; if(y<=mid)add(idx<<1,x,y,z); else if(x>mid)add(idx<<1|1,x,y,z); else add(idx<<1,x,y,z),add(idx<<1|1,x,y,z); update(idx);}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) { d[i].L=read(),d[i].R=read(); a[++cnt]=d[i].L,a[++cnt]=d[i].R; d[i].len=d[i].R-d[i].L; } sort(a+1,a+1+cnt); cnt=unique(a+1,a+1+cnt)-a-1; sort(d+1,d+1+n,cmp); for(int i=1;i<=n;i++) { d[i].L=lower_bound(a+1,a+1+cnt,d[i].L)-a; d[i].R=lower_bound(a+1,a+1+cnt,d[i].R)-a; } int ans=INF,top=0; build(1,1,cnt); for(int i=1;i<=n;i++) { while(top<n&&t[1].maxn<m) { ++top; add(1,d[top].L,d[top].R,1); } if(t[1].maxn>=m)ans=min(ans,d[top].len-d[i].len); add(1,d[i].L,d[i].R,-1); } if(ans==INF)printf("-1\n"); else printf("%d\n",ans); return 0;}
[UOJ #222][NOI2016]区间（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。