Zerojudge b966
題敘
https://zerojudge.tw/ShowProblem?problemid=b966
給定多個線段,求所有線段除去覆蓋部分的長度總和
想法
將所有線段排序後將完全覆蓋的線段除去
接下來的線段只需討論是否有重疊部分,若有,則將線段界線更新
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include<bits/stdc++.h> #define LL long long #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define pii pair<int,int> using namespace std; int n; vector<pii> v,res; int main(){ IOS cin>>n; for(int i=0,l,r ; i<n ; i++){ cin>>l>>r; v.emplace_back(l,r); } sort(v.begin(),v.end()); int Max=0; for(auto i: v){ if(i.second>Max){ res.push_back(i); Max=i.second; } } int ans=0; for(int i=0 ; i<res.size()-1 ; i++){ if(res[i].second>=res[i+1].first){ res[i+1].first=res[i].first; } else{ ans+=res[i].second-res[i].first; } } ans+=res[res.size()-1].second-res[res.size()-1].first; cout<<ans<<"\n";
return 0; }
|
複雜度
排序複雜度 $O(nlogn)$
搜尋答案複雜度 $O(n)$
總複雜度 $O(n+nlogn)$