洛谷题解UVA排序扫描线题解:UVA11776 Oh Your Royal Greediness!
xyx404
简要题意:
多组数据。
每组数据给定 n(0≤n≤1000)个区间 [si,ei](0≤si≤ei≤31536000),求所有时刻中同时存在的区间数量的最大值。
思路:
考虑扫描线算法。
对于扫描线的基本步骤,可以参考此博文。
将每个区间的开始点和结束点存下来,然后按照时间顺序排序,如果是起点让计数器加一,否则是终点让计数器减一,我们只需要在计算器里取最大值就好了。
因为终点也算在区间里,所以我们在处理时要优先处理起点。
对于每组数据,时间复杂度为 O(nlogn)。
代码:
#include<bits/stdc++.h> using namespace std; #define LL long long #define itn int #define ull unsigned long long int n; int Case_Cnt=0; struct node{ int x,lx; friend bool operator<(node x,node y){ return x.x!=y.x?x.x<y.x:x.lx>y.lx; } }; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); while(cin>>n){ if(n==-1)break; int ans=0; cout<<"Case "<<++Case_Cnt<<": "; vector<node>sz; for(int i=1;i<=n;i++){ int s,e; cin>>s>>e; sz.emplace_back(node{s,1}); sz.emplace_back(node{e,-1}); } sort(sz.begin(),sz.end()); int now=0; for(int i=0;i<n*2;i++){ ans=max(ans,now); now+=sz[i].lx; } ans=max(ans,now); cout<<ans<<"\n"; } return 0; }
|