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

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

http://uoj.ac/problem/222

在數軸上有 n個閉區間 [l1,r1],[l2,r2],...,[ln,rn]。現在要從中選出 m 個區間，使得這 m個區間共同包含至少一個位置。換句話說，就是使得存在一個 x，使得對于每一個被選中的區間 [li,ri]，都有 li≤x≤ri。

對于一個合法的選取方案，它的花費為被選中的最長區間長度減去被選中的最短區間長度。區間 [li,ri] 的長度定義為 ri?li，即等于它的右端點的值減去左端點的值。 求所有合法方案中最小的花費。如果不存在合法的方案，輸出 ?1。

（天哪我終于會做套路題了……雖然對于判斷是否合法的時候沒想到線段樹……）

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

然而相比于一個點被覆蓋m次，更難處理的是這個答案的運算。

于是我們將區間按照權值排序，接著就是兩個指針不斷擴大，當合法的時候更新一下答案就行了。

那么如何維護一個點被最多被覆蓋了多少次呢？線段樹唄。

注意空間不要開小了-=-

#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。 　　　　　　　　　　　　　　+

?+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/+

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

轉載于:https://www.cnblogs.com/luyouqi233/p/9132055.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

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

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