Loading...

二分答案 专题训练

check评论:0 条 remove_red_eye浏览量:465 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-13

$NOIP$就要来了qwq

我要练练二分

我们一般对于求"最大值的最小值"这一类题目,通过二分答案,再进行检验,可以很快得出答案,要注意的是,我们所求的答案一定要满足单调性,即如果我们的答案变大,那么$check$出来的$ans$一定会是单调增减的,判断存在性的问题,$check$出来的$ans$不会有左端点可以,右端点可以而中间不行这种情况,这样的话我们就可以二分将$O(n)$优化为$O(log\ n)$

  • 洛谷$P1462$ 通往奥格瑞玛的道路

见我的博客

  • 洛谷$P2498$ [SDOI2012]拯救小云公主

我们二分最短长度,然后$spfa$即可,每次走一个点需要判断与其最近的$boss$的距离

可惜这样现在会$TLE$了...

所以只能以下方代码的思想,直接$spfa$

#include <bits/stdc++.h>
using namespace std;
int x[3010],y[3010],head[3010],vis[3010],cnt;
double dis[3010];
double mmp[3010][3010];
int k,n,m;
double getmydis(int a,int b,int c,int d)
{
    return sqrt((a-c)*(a-c)+(b-d)*(b-d))/2;
}
void spfa()
{
    fill(dis,dis+3005,2147483646.9);
    memset(vis,0,sizeof(vis));
    queue<int> q;
    vis[0]=1;
    dis[0]=0;
    q.push(0);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=0;i<=k+1;i++)
        {
            if(i==u)
            {
                continue;
            }
            if(dis[i]>max(dis[u],mmp[u][i]))
            {
                dis[i]=max(dis[u],mmp[u][i]);
                if(!vis[i])
                {
                    q.push(i);
                    vis[i]=1;
                }
            }
        }
    } 
}
int main()
{
    cin>>k>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        double m1=min(abs(n-x[i]),abs(y[i]-1));
        double m2=min(abs(x[i]-1),abs(m-y[i]));
        mmp[0][i]=mmp[i][0]=m1;
        mmp[i][k+1]=mmp[k+1][i]=m2;
        for(int j=1;j<i;j++)
        {
            double z=getmydis(x[i],y[i],x[j],y[j]);
            mmp[i][j]=mmp[j][i]=z;
        }
    }
    mmp[0][k+1]=mmp[k+1][0]=0x3f3f3f3f;
    spfa();
    printf("%.2lf",dis[k+1]);
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名