首页 > ACM题库 > HDU-杭电 > HDU 3585-maximum shortest distance-分治-[解题报告]HOJ
2014
11-27

HDU 3585-maximum shortest distance-分治-[解题报告]HOJ

maximum shortest distance

问题描述 :

There are n points in the plane. Your task is to pick k points (k>=2), and make the closest points in these k points as far as possible.

输入:

For each case, the first line contains two integers n and k. The following n lines represent n points. Each contains two integers x and y. 2<=n<=50, 2<=k<=n, 0<=x,y<10000.

输出:

For each case, the first line contains two integers n and k. The following n lines represent n points. Each contains two integers x and y. 2<=n<=50, 2<=k<=n, 0<=x,y<10000.

样例输入:

3 2
0 0
10 0
0 20

样例输出:

22.36

    这道题是学习了最大团过程中遇到的一道题目,最大团学习中的体会就是搜索的基本功还是不扎实,最大团是一个NP完全问题(不懂装懂了),现在还没多项式算法,只能靠启发式搜索或者是回溯来实现了。回溯法也可以通过各种剪枝来优化。

    回到这道题目,意思就是给定平面上一些点,求出K个点满足其实每个点的距离都大于M,求M.

    通过不断的二分距离,如果距离大于二分出来的距离,那么就建边,求出最大团,就是满足距离大于M的最大个数,然后就是无限TLE。因为我是通过直接二分它们之间的距离,但是这道题目的特殊性就在于,最终二分出来的值必定是某两个点之间的距离,我们具体在操作的时候相当于可以直接离散化,把所有的距离预处理出来,然后直接对这些个别距离进行二分。终于700ms+水过了。。。这个方法感觉非常实用的一个小技巧maximum shortest distance。继续加油

 

 

#include<stdio.h>
#include<math.h>
#include<iostream>
#define eps 1e-7
using namespace std;

int n,k,vis[55],tmax,dp[55],ji;
int locat[55][2],map[55][55];
double dis[55][55],distan[2000];

int cmp(const void *a,const void*b)
{
    return *(double *)a>*(double *)b?1:-1;
}

void build(int mid)
{
    int i,f;
    for(i=1;i<=n;i++)
    {
        for(f=1;f<=n;f++)
        {
            if(dis[i][f] >= distan[mid]-eps)
            {
                map[i][f]=1;
            }
            else
            {
                map[i][f]=0;
            }
        }
        map[i][i]=0;
    }
}

void dfs(int id,int cnt)
{
    int tvis[55],i,f,able=0;
    for(i=id+1;i<=n;i++)
    {
        if(1 == vis[i])
        {
            able++;
        }    
    }
    if(0 == able)
    {
        tmax=max(tmax,cnt);
    }    
    if(cnt + able <= tmax)
    {
        return ;
    }
    for(i=1;i<=n;i++)
    {
        tvis[i]=vis[i];
    }
    for(i=id+1;i<=n;i++)
    {
        if(0 == tvis[i])
        {
            continue;    
        }
        if(cnt +dp[i] <= tmax)
        {
            continue;    
        }
        for(f=id+1;f<=n;f++)
        {
            vis[f]=tvis[f]&map[i][f];
        }
        dfs(i,cnt+1);
    }
}

int max_clique()
{
    int i,f;
    tmax=1;
    dp[n]=1;
    for(i=n-1;i>=1;i--)
    {
        for(f=1;f<=n;f++)
        {
            vis[f]=map[i][f];
        }    
        dfs(i,1);
        dp[i]=tmax;
        if(n == tmax)
        {
            return tmax;
        }
    }
    return tmax;
}

double bs()
{
    int l=0,r=ji,mid;
    while(l != r-1)
    {
        mid=(l+r)>>1;    
        build(mid);        
        if(k <= max_clique())
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    } 
    return distan[l];
}

int main()
{
    int i,f,g,sum;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        ji=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&locat[i][0],&locat[i][1]);
        }
        for(i=1;i<=n;i++)
        {
            for(f=1;f<=n;f++)
            {
                sum=0;
                for(g=0;g<2;g++)
                {
                    sum+=(locat[i][g]-locat[f][g])*((locat[i][g]-locat[f][g]));
                }
                dis[i][f]=sqrt((double)sum);
                if(i > f)
                {
                    distan[ji]=dis[i][f];
                    ji++;
                }
            }
        }
        qsort(distan,ji,sizeof(distan[0]),cmp);        
        printf("%.2lf\n",bs());
    }
    return 0;
}

 

参考:http://blog.csdn.net/qq564690377/article/details/7983972


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。