题意：给你一些区间，再查询一些点，问这些点与所有区间形成的最小距离的最大值。最小距离定义为：如果点在区间内，那么最小距离为0，否则为min(pos-L[i],R[i]-pos)。
解法：当然要排个序，仔细想想会发现我们要找的区间的位置满足二分性质，即如果此时pos-L[mid] >= R[mid]-pos，那么我们要找的区间肯定是mid或大于mid，否则，我们要找的区间一定是mid即mid以下。二分找到即可。预处理时要把嵌套在别的区间里的区间忽略掉，因为外面那个区间一定比他更优。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #define ll long long using namespace std; #define N 100007 #define M 22 struct node { ll l,r; }p[N],np[N]; ll L[N],R[N]; int tot; ll pos; int cmp(node ka,node kb) { return ka.l < kb.l; } ll get(int mid) { if(mid > tot || mid < 1) return 0; if(L[mid] > pos || R[mid] < pos) return 0; return min(pos-L[mid],R[mid]-pos); } int main() { int t,cs = 1,n,m,i,j; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%lld%lld",&p[i].l,&p[i].r); sort(p+1,p+n+1,cmp); tot = 1; for(i=2;i<=n;i++) { if(p[i].r > p[tot].r) { tot++; p[tot] = p[i]; } } for(i=1;i<=tot;i++) { L[i] = p[i].l; R[i] = p[i].r; } printf("Case %d: ",cs++); while(m--) { int ans = 0; scanf("%lld",&pos); int low,high; low = 1,high = tot; while(low <= high) { int mid = (low+high)/2; if(R[mid]-pos <= pos-L[mid]) low = mid+1; else high = mid-1; } printf("%lld ",max(get(low),get(high))); } } return 0; }