F. The Treasure of The Segments
题意：
给n个区间[l,r]
求删去多少个区间，可以使得剩余区间中，有一个区间可以和其他区间向连接(有相同的子区间或相同的端点即相连接)
思路：
先按l排序，对于每个区间，找到大于r的最小下标，n-index即为区间右方右边不与这个区间相连的区间数量
同理，按r排序找到区间左方不与这个区间相连的区间数量
然后去找一个最小值即可
代码：
#include<bits/stdc++.h> #define ll long long using namespace std; struct node{ int l,r,id; friend bool operator <(node a,node b){ if(a.l==b.l) return a.r<b.r; else return a.l<b.l; } }a[200005]; struct node2{ int l,r,id; friend bool operator <(node2 a,node2 b){ if(a.r==b.r) return a.l<b.l; else return a.r<b.r; } }b[200005]; map<int,int>sum; int n; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); sum.clear(); for(int i=0;i<n;i++){ int l,r; scanf("%d%d",&l,&r); a[i].l=l;a[i].r=r;a[i].id=i; b[i].l=l;b[i].r=r;b[i].id=i; } sort(a,a+n); sort(b,b+n); vector<int>a1; vector<int>b1; for(int i=0;i<n;i++)a1.push_back(a[i].l); for(int i=0;i<n;i++)b1.push_back(b[i].r); for(int i=0;i<n;i++){ int x; x=upper_bound(a1.begin(),a1.end(),a[i].r)-a1.begin(); sum[a[i].id]+=n-x; x=lower_bound(b1.begin(),b1.end(),b[i].l)-b1.begin(); sum[b[i].id]+=x; } int ans=n-1; for(int i=0;i<n;i++){ ans=min(sum[i],ans); } printf("%d\n",ans); } }
F. The Treasure of The Segments
原文：https://www.cnblogs.com/xuanzo/p/14145225.html