[HDOJ3373 Point]枚举+小优化 || 离散化+线段树+平衡树+二分答案

【题目大意】

定义点与点之间的距离为max(|Xi-Xj|,|Yi-Yj|)

给定N个点，将这N个点中每个点与最近点的距离加起来，输出SUM。

【算法分析】

算法1：

算了下复杂度O(N^2)的话加些优化应该可以卡过。

于是我把他们按x排序，x相等的按y排序。

然后枚举当前点i，并向前和向后枚举点j，如果出现abs(X[j]-X[i])>=now （其它now为当前答案），那么可以break退出循环。（最优化剪枝）

然后这样就可以9000MS左右AC了。

算法2：

同算法1那样排序。

再按X坐标离散化。

然后枚举当前点i，并二分答案（当前最短距离）。

问题转化为看是否存在点(X[j],Y[j])，使得abs(X[j]-X[i])<=ANS 且 abs(Y[j]-Y[i])<=ANS

于是就可以以X轴为线段树所划分的区间建立一棵线段树，线段树上再建立一棵以Y坐标为key值的平衡树。

然后在上面进行查找。每次查找的复杂度是O((lgN)^2)。

加上二分答案，每个点的处理复杂度为O((lgN)^3)。

所以总时间复杂度为O(N (lgN)^3 )。

空间复杂度为O(NlgN)。

因为最同一深度的线段树区间下，一个点只能出现在一个区间内。所以一个点最多出现lgN次。所以空间复杂度不是问题。

但是这个算法编程复杂度可能比较高。如果用STL的

【其它】由于我不会STL，所以算法2就不写了。。。

【CODE】

#include #include #include #include #include using namespace std;
const int N=101111;
const int INF=0x7FFFFFFF;
int n;
struct type{int x,y;}L[N];
long long ans;

inline bool cmp(type x,type y){
    if (x.x    if (x.x>y.x) return false;
    if (x.y    return false;
}   

void input(){
    for (int i=1;i<=n;i++)
      scanf("%d%d",&L[i].x,&L[i].y);
    sort(&L[1],&L[n+1],cmp);
}   

void work(){
    ans=0;
    int i,j,now;
    for (i=1;i<=n;i++){
        now=INF;
       
        j=i-1;
        while (j){
            if (L[i].x-L[j].x>=now) break;
            now            j–;
        }   

        j=i+1;
        while (j<=n){
            if (L[j].x-L[i].x>=now) break;
            now            j++;
        }   
       
        ans+=now;
    }   
    cout << ans << endl;
}   

int main(){
    while (scanf("%d",&n)!=EOF){
        input();
        work();
    }   
}