题目大意：给定$n$个区间$[l_i,r_i]$，选出$m$个区间使它们有一个共同的位置$x$，且使它们产生的费用最小。求最小费用。费用定义为最长的区间长度减去最短区间长度。
-----------------
因为区间顺序改动又不影响答案，我们不妨按照长度排个序。看到数据范围果断离散化。
思考一种最朴素的做法：将排好序的区间逐一加入数轴，看有没有一个点被覆盖的次数$\geq m$。
有的话就统计一下答案，然后将前面加入的数删掉，直到$<m$。
显然用到了尺取法。维护是否有一个点被覆盖的次数可以用线段树。
然后就可以成功A掉此题。
代码：
#include<bits/stdc++.h> using namespace std; int n,m,maxx,b[1000005],cnt,size,head=0,tail=0,ans=0x3f3f3f3f; struct node { int l,r,len; }a[500005]; struct tree { int index,l,r,max,lazy; }tree[4000005]; inline int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} return x*f; } bool cmp(node x,node y) { return x.len<y.len; } inline void build(int index,int l,int r) { tree[index].l=l; tree[index].r=r; if (l==r) return; int mid=(l+r)>>1; build(index*2,l,mid); build(index*2+1,mid+1,r); } inline void pushdown(int index) { tree[index*2].lazy+=tree[index].lazy; tree[index*2+1].lazy+=tree[index].lazy; tree[index*2+1].max+=tree[index].lazy; tree[index*2].max+=tree[index].lazy; tree[index].lazy=0; } inline void update(int index,int l,int r,int x) { if (l<=tree[index].l&&tree[index].r<=r) { tree[index].max+=x; tree[index].lazy+=x; return; } if (tree[index].lazy) pushdown(index); int mid=(tree[index].l+tree[index].r)>>1; if (l<=mid) update(index*2,l,r,x); if (r>mid) update(index*2+1,l,r,x); tree[index].max=max(tree[index*2+1].max,tree[index*2].max); } int main() { n=read(),m=read(); for (int i=1;i<=n;i++) { a[i].l=read(),a[i].r=read();a[i].len=a[i].r-a[i].l; b[++cnt]=a[i].l;b[++cnt]=a[i].r; } sort(b+1,b+cnt+1); size=unique(b+1,b+cnt+1)-b-1; sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++) { a[i].l=lower_bound(b+1,b+size+1,a[i].l)-b; a[i].r=lower_bound(b+1,b+size+1,a[i].r)-b; maxx=max(maxx,a[i].r); } build(1,1,maxx); while(tail<n) { while(tree[1].max<m&&tail<=n){tail++;update(1,a[tail].l,a[tail].r,1);} if (tree[1].max<m) break; while(head<=tail&&tree[1].max>=m) { head++;update(1,a[head].l,a[head].r,-1); ans=min(ans,a[tail].len-a[head].len); } } if (ans==0x3f3f3f3f) printf("-1"); else printf("%d",ans); return 0; }
原文链接: https://www.cnblogs.com/Invictus-Ocean/p/13346599.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368912
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
