平面上最近点对问题

题目

题解

题目公式等价于f(i,j)=(j-i)^2+(presumj-presumi)^2;因此，可以转化为求平面上的最近点对问题。

代码

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cmath>  
using namespace std;  
typedef __int64 LL;  
const int maxn=100010;  
const LL INF=LL(9e18);  

struct Node{  
    LL x,y;  
}ns[maxn];  

int n,tmp[maxn];  

bool cmpY(const Node& nd1,const Node& nd2){  
    return nd1.y<nd2.y;  
}  

LL sqr(LL x){ return x*x; }  
LL min(LL x,LL y){ return x>y?y:x; }  

LL solve(int l,int r){  
    if(l==r) return INF;  
    int mid=l+(r-l)/2,i,j,tot=0;  
    LL xm=ns[mid].x;  
    LL res=min(solve(l,mid),solve(mid+1,r));  
    inplace_merge(ns+l,ns+mid+1,ns+r+1,cmpY);  
    for(i=l;i<=r;i++){  
        if(sqr(ns[i].x-xm)<=res) tmp[tot++]=i;  
    }  
    for(i=0;i<tot;i++){  
        int p1=tmp[i];  
        for(j=i+1;j<tot;j++){  
            int p2=tmp[j];  
            if(sqr(ns[p2].y-ns[p1].y)>res) break;  
            LL dis=sqr(ns[p2].y-ns[p1].y)+sqr(ns[p2].x-ns[p1].x);  
            res=min(res,dis);  
        }  
    }  
    return res;  
}  

int main() {  
    int i,j;  
    scanf("%d",&n);  
    int sumv=0,v;  
    for(i=1;i<=n;i++){  
        ns[i].x=i;  
        scanf("%d",&v);  
        sumv+=v;  
        ns[i].y=sumv;  
    }  
    printf("%I64d\n",solve(1,n));  
    return 0;  
}