首页 > 代码库 > UVALive 6656 Watching the Kangaroo --二分

UVALive 6656 Watching the Kangaroo --二分

2024-07-18 12:23:46   212人阅读

题意：给你一些区间，再查询一些点，问这些点与所有区间形成的最小距离的最大值。最小距离定义为：如果点在区间内，那么最小距离为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 longusing namespace std;#define N 100007#define M 22struct 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:\n",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\n",max(get(low),get(high)));        }    }    return 0;}
View Code

 


联系
我们