首页 > 代码库 > 【NOI2016】区间 题解
【NOI2016】区间 题解
题目大意：
有n个区间，当有m个区间有公共部分时，求m个区间长度的最大值与最小值之差的最小值。
思路：
按区间的长度从小到大排序，可知连续的几个区间最优，则用两个指针指其头尾，线性扫描，再用线段树区间覆盖。
代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #define N 1000009 5 #define INF 2147483647 6 using namespace std; 7 8 int n,m,i,j,cnt,ans=INF,sum[N<<2],lazy[N<<2],b[N<<1]; 9 struct node{ int l,r,len; } a[N];10 11 bool cmp(const node &x,const node &y)12 {13 return x.len<y.len;14 }15 16 int find(int l,int r,int x)17 {18 if (l==r) return l;19 int mid=l+r>>1;20 if (x<=b[mid]) find(l,mid,x);21 else find(mid+1,r,x);22 }23 24 void up_date(int k,int x)25 {26 sum[k]+=x,lazy[k]+=x;27 }28 29 void change(int cur,int L,int R,int l,int r,int val)30 {31 if (L==l && R==r) { up_date(cur,val); return; }32 int mid=L+R>>1;33 if (lazy[cur])34 {35 up_date(cur<<1,lazy[cur]);36 up_date(cur<<1|1,lazy[cur]);37 lazy[cur]=0;38 }39 if (r<=mid) change(cur<<1,L,mid,l,r,val);40 else if (l>mid) change(cur<<1|1,mid+1,R,l,r,val);41 else change(cur<<1,L,mid,l,mid,val),change(cur<<1|1,mid+1,R,mid+1,r,val);42 sum[cur]=max(sum[cur<<1],sum[cur<<1|1]);43 }44 45 void solve()46 {47 for (i=1;i<=n;i++)48 {49 while (sum[1]<m)50 {51 if (j==n) return; j++;52 change(1,1,cnt,a[j].l,a[j].r,1);53 }54 ans=min(ans,a[j].len-a[i].len);55 change(1,1,cnt,a[i].l,a[i].r,-1);56 }57 }58 59 int main()60 {61 scanf("%d%d",&n,&m);62 for (i=1;i<=n;i++)63 {64 scanf("%d%d",&a[i].l,&a[i].r);65 b[++cnt]=a[i].l,b[++cnt]=a[i].r;66 a[i].len=a[i].r-a[i].l;67 }68 sort(a+1,a+n+1,cmp),sort(b+1,b+cnt+1);69 for (i=1;i<=n;i++) a[i].l=find(1,cnt,a[i].l),a[i].r=find(1,cnt,a[i].r);70 solve(); printf("%d\n",ans<INF?ans:-1);71 return 0;72 }
【NOI2016】区间 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。