2018-11-29-poj-3485

题目:POJ-3485

其实题目不是很难，很快就过了，只是在过了之后看到别人的时间明显比我的要短，就忍不住优化了一下。

第一次：

#include<stdio.h>
#include<math.h>

#define N 10000

struct pos
{
    int x,y;
    double s,e;
};

int main(void)
{
    int l,d,n;
    int i,j,cnt;
    struct pos a[N];
    double tmp;
    while(scanf("%d%d%d",&l,&d,&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].e = sqrt(d*d-a[i].y*a[i].y);
            a[i].s = a[i].x - a[i].e;
            a[i].e = a[i].x + a[i].e;
            if(a[i].s < 0)
                a[i].s = 0;
            if(a[i].e > l)
                a[i].e = l;
        }
        for(cnt=0;n>0;n=j)
        {
            cnt++;
            tmp = a[0].e;
            for(i=0,j=0;i<n;i++)
                if(a[i].s > tmp)
                    a[j++] = a[i];
        }
        printf("%d\n",cnt);
    }
    return 0;
}

第二次：

#include<cstdio>
#include<cmath>
#include<algorithm>

#define N 10000

using namespace std;

struct pos
{
    double s,e;
};

int cmp(struct pos a1,struct pos a2)
{
    if(a1.s < a2.s)
        return 1;
    if(a1.s > a2.s)
        return 0;
    if(a1.e > a2.e)
        return 1;
    return 0;
}

int main(void)
{
    int l,d,n;
    int i,cnt,x,y;
    struct pos a[N];
    double tmp;
    while(scanf("%d%d%d",&l,&d,&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            a[i].e = sqrt(d*d-y*y);
            a[i].s = x - a[i].e;
            a[i].e = x + a[i].e;
            if(a[i].s < 0)
                a[i].s = 0;
            if(a[i].e > l)
                a[i].e = l;
        }
        sort(a,a+n,cmp);
        for(cnt=1,i=1,tmp=a[0].e;i<n;i++)
        {
            if(tmp<a[i].s)
            {
                tmp = a[i].e;
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

两次的不同点在于：
第一次：

for(cnt=0;n>0;n=j)
{
    cnt++;
    tmp = a[0].e;
    for(i=0,j=0;i<n;i++)
        if(a[i].s > tmp)
            a[j++] = a[i];
}

第二次：

sort(a,a+n,cmp);
for(cnt=1,i=1,tmp=a[0].e;i<n;i++)
{
    if(tmp<a[i].s)
    {
        tmp = a[i].e;
        cnt++;
    }
}

在最优的情况下，几乎是前者更快，但基本不明显，毕竟两者均为O(n)，在最坏的情况下，前者时间复杂度为O(n2),后者O(n),性能下降明显。在最优的情况下，第二次额外多了一次排序，虽说是104，但也只能说STL大法好。