Question

杭电acm1007题，为什么总是时间超限

这是我自己编写的程序，请大神帮我修改一下，或者说一下该题解决的详细步骤.
#include<stdio.h>#include<math.h>int main(){ double x[10000],y[10000],d[10010],l[10010],m,k,j; int i,n; while(scanf("%d",&n),n) { for(i=0;i<n;i++) scanf("%lf %lf",&x[i],&y[i]); for(i=0;i<n;i++) { if(x[i]<x[i+1]) { j=x[i+1]; x[i+1]=x[i]; x[i]=j; } if(y[i]<y[i+1]) { j=y[i+1]; y[i+1]=y[i]; y[i]=j; } } for(i=1;i<n;i++) { d[i]=(x[i]-x[i-1]); l[i]=(y[i]-y[i-1]); } m=d[1];k=l[1]; for(i=1;i<n;i++) { if(m>d[i]) { j=m; m=d[i]; d[i]=j; } if(k>l[i]) { j=k; k=l[i]; l[i]=j; } } m=sqrt(k*k+m*m); m=m/2; printf("%.2lf\n",m); } return 0;}

Answer 1

楼主，首先你的算法是O(n)的，所以怎么都不应该超时，所以只要稍微一看，就知道你的数组开小了，人家的数组要求是100000的，你少了个0……

另外，在main函数里面开100000的数组会爆栈的，所以应该将数组放到外面作为全局变量。

然后，其实你得算法是有问题的，人家题目要让你求的是二维平面的最近点对的距离的一半，你的O(n)算法，很明显不对吧…你应该考虑用分治算法，把平面的点对分成左右两份，弄出左右两份的最短距离，然后合起来弄这两份之间的最短距离。

我挫挫的写了个代码，算是分治，但是基本没什么优化，只能说应该用分治来做，楼主你将就着看看吧。为了方便，我用了C++的STL，因为要排序。

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define N 100100

struct point
{
    double x, y;
    friend bool operator<(const point &a, const point &b)
    {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
}pnt[N];

int n;
double ans;

double min(double a, double b)
{
    return a < b ? a : b;
}

double sqr(double x)
{
    return x * x;
}

double dis(const point &a, const point &b)
{
    return sqr(a.x - b.x) + sqr(a.y - b.y);
}

void run(int a, int b)
{
    if (b - a <= 10)
    {
        for (int i = a;i<=b;i++)
        {
            for (int j = i + 1;j <= b;j++)
            {
                ans = min(ans, dis(pnt[i],pnt[j]));
            }
        }
        return ;
    }
    int m = a + b >> 1;
    run(a, m);
    run(m + 1, b);
    for (int i = a;a < m;a++)
    {
        for (int j = m + 1;j<b;j++)
        {
            double d = dis(pnt[i], pnt[j]);
            if (d >= ans)
                break;
            ans = d;
        }
    }            
}

int main()
{
    while(scanf("%d",&n),n)
    {
        for (int i = 0;i<n;i++)
        {
            scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
        }
        sort(pnt, pnt + n);
        ans = 1e200;
        run(0, n - 1);
        printf("%.2lf\n",sqrt(ans) / 2);
    }
    return 0;
}

Answer 2

我建议楼主，既然你是专业写代码的，那么提问也专业点，贴代码应该用代码格式，这种不分行的代码我看到一律都不回答的。