https://www.lydsy.com/JudgeOnline/problem.php?id=4653

https://www.luogu.org/problemnew/show/P1712

http://uoj.ac/problem/222

在數(shù)軸上有 n個(gè)閉區(qū)間 [l1,r1],[l2,r2],...,[ln,rn]。現(xiàn)在要從中選出 m 個(gè)區(qū)間，使得這 m個(gè)區(qū)間共同包含至少一個(gè)位置。換句話(huà)說(shuō)，就是使得存在一個(gè) x，使得對(duì)于每一個(gè)被選中的區(qū)間 [li,ri]，都有 li≤x≤ri。

對(duì)于一個(gè)合法的選取方案，它的花費(fèi)為被選中的最長(zhǎng)區(qū)間長(zhǎng)度減去被選中的最短區(qū)間長(zhǎng)度。區(qū)間 [li,ri] 的長(zhǎng)度定義為 ri?li，即等于它的右端點(diǎn)的值減去左端點(diǎn)的值。 求所有合法方案中最小的花費(fèi)。如果不存在合法的方案，輸出 ?1。

（天哪我終于會(huì)做套路題了……雖然對(duì)于判斷是否合法的時(shí)候沒(méi)想到線(xiàn)段樹(shù)……）

看復(fù)雜度是O(nlogn)猜想可能又是枚舉左端點(diǎn)找右端點(diǎn)的套路。

然而相比于一個(gè)點(diǎn)被覆蓋m次，更難處理的是這個(gè)答案的運(yùn)算。

于是我們將區(qū)間按照權(quán)值排序，接著就是兩個(gè)指針不斷擴(kuò)大，當(dāng)合法的時(shí)候更新一下答案就行了。

那么如何維護(hù)一個(gè)點(diǎn)被最多被覆蓋了多少次呢？線(xiàn)段樹(shù)唄。

注意空間不要開(kāi)小了-=-

#include<cmath> #include<stack> #include<queue> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int INF=2e9; const int N=5e5+5; inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } struct range{int l,r,w; }g[N]; int n,m,lim,b[2*N],tr[8*N],lz[8*N]; inline bool cmp(range a,range b){return a.w<b.w; } inline void LSH(){sort(b+1,b+lim+1);lim=unique(b+1,b+lim+1)-b-1;for(int i=1;i<=n;i++){g[i].l=lower_bound(b+1,b+lim+1,g[i].l)-b;g[i].r=lower_bound(b+1,b+lim+1,g[i].r)-b;} } inline void push(int a){if(!lz[a])return;lz[a<<1]+=lz[a];lz[a<<1|1]+=lz[a];tr[a<<1]+=lz[a];tr[a<<1|1]+=lz[a];lz[a]=0; } void insert(int a,int l,int r,int l1,int r1,int w){if(r<l1||r1<l)return;if(l1<=l&&r<=r1){tr[a]+=w;lz[a]+=w;return;}push(a);int mid=(l+r)>>1;insert(a<<1,l,mid,l1,r1,w);insert(a<<1|1,mid+1,r,l1,r1,w);tr[a]=max(tr[a<<1],tr[a<<1|1]); } int main(){n=read(),m=read();for(int i=1;i<=n;i++){g[i].l=b[++lim]=read();g[i].r=b[++lim]=read();g[i].w=g[i].r-g[i].l;}LSH();sort(g+1,g+n+1,cmp);int l=1,ans=INF;for(int l=1,r=0;l<=n;l++){while(r<n&&tr[1]<m){r++;insert(1,1,lim,g[r].l,g[r].r,1);}if(tr[1]>=m)ans=min(ans,g[r].w-g[l].w);insert(1,1,lim,g[l].l,g[l].r,-1);}printf("%d\n",ans==INF?-1:ans);return 0; }

+++++++++++++++++++++++++++++++++++++++++++

?+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

?+歡迎訪問(wèn)我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

轉(zhuǎn)載于:https://www.cnblogs.com/luyouqi233/p/9132055.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的BZOJ4653 洛谷1712 UOJ222：[NOI2016]区间——题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。