[二分]SSL 2135 难题

传送门

Description

平面上有N个点，SubRaY想在其中找出一个点，使之到其它点的距离之和最小。为了便于计算，所以我们定义(x1,y1)(x2,y2)两点间的距离为：|x2-x1|+|y2-y1|
请你编写一个程序，来完成此任务：输出距离总和的最小值是多少。

题解

这题其实就是求不连续的最长不下降子序列
用二分判断这个数是否满足连续

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,i,a,f[100001],l,j;
int find(int l,int r,int x)
{
    int mid=(l+r)/2;
    if (l>r) return l;
    if (x==f[mid]) return mid;
    else if (x<f[mid]) find(mid+1,r,x);
         else find(l,mid-1,x);
}
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a);
        if (a==0) continue;
        j=find(1,l,a);
        if (j>l){ l++; f[l]=a; } else f[j]=a;
    }
    printf("%d",l);
}