CF1462F The Treasure of The Segments 题解

紊莫 · 2024-01-05 19:05:52 · 题解

首先有一个重要的转化：最少的删除次数就是相离的线段条数，那么我们可以贪心地找相离条数最小的即为答案。

这样就很简单了，考虑 i 和 j 相离的条件，l_i>r_j 或 r_i<l_j，显然这两者不可能同时满足，那么直接分别计算再相加求最值即可。

核心代码如下。

cin>>n;
F(i,1,n){
    cin>>L[i]>>R[i];
    x[i]={L[i],R[i]};
}
sort(L+1,L+n+1);
sort(R+1,R+n+1);
int ans=inf;
F(i,1,n){
    int a=upper_bound(L+1,L+n+1,x[i].r)-L-1;a=n-a;
    int b=lower_bound(R+1,R+n+1,x[i].l)-R-1;
    ans=min(ans,a+b);
}
cout<<ans<<'\n';