F. The Treasure of The Segments
理解题意就是要让我们找一个线段+他相交的所有线段max
我们暴力枚举线段 然后用sum-不相交的
不相交的就好算了 只有两种情况
一个线段左端点>r 一个线段的右端点<l
我们每次二分查找即可
void solve() {
int n;cin>>n;
vector<pair<int,int>>s;
vector<int>a,b;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
s.push_back({x,y});
a.push_back(x);
b.push_back(y);
}
sort(all(a));
sort(all(b));
std::reverse(b.begin(), b.end());
int ans=INF;
for(int i=0;i<n;i++){
auto [x,y]=s[i];
int t1=upper_bound(all(a),y)-a.begin();
int t2=upper_bound(all(b),x,greater<>())-b.begin();
ans=min(ans,(n-t1)+(n-t2));
}
cout<<ans<<endl;
}
标签:690,int,线段,Codeforces,相交,back,ans,push,Div
From: https://www.cnblogs.com/ycllz/p/16830166.html