Description

在數軸上有 n個閉區間 [l1,r1],[l2,r2],...,[ln,rn]?，F在要從中選出 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 0x3f3f3f3f using 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; }

?

轉載于:https://www.cnblogs.com/Zars19/p/6806481.html

總結

以上是生活随笔為你收集整理的[UOJ #222][NOI2016]区间（线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。