一本通第二章-二分与三分 题解

access_time    bookmark 题解    comment 0 条评论   

10011.愤怒的牛

二分答案,然后贪心进行验证,即只要达到了枚举的距离能放就放,如果最后能放下就验证成功。

int n,m,ans,s[100005];

inline bool check(int x)
{
    int now=1;
    for (int i=1;i<m;i++)
    {
        int j=now+1;
        while (s[now]+x>s[j] && j<=n) j++;
        if (j>n) return 0;
        now=j;
    }
    return 1;
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+n+1);
    int l=0,r=s[n]-s[1];
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    printf("%d",ans);
    return 0;
}

10012.Best Cow Fences

对浮点数二分答案,然后进行验证。

验证的思想是数列中每一个数减去当前枚举的数,然后只要找到一段长度 $\geq L$ 的子序列且和 $\le 0$ 就验证成功。

我们对减去枚举答案后的子序列取前缀和,然后枚举子序列的右端点,同时维护序列左端点或以前的最小值,最后把右端点与之差分就可以得到当前最大值。每次枚举得到的最大值只要有一个 $\geq 0$ 那么就验证成功。

还有个问题是我也不知道为什么最后答案取 $l$ 就总是要小 $1$ ,加大精度到 $1e-15$ 才能过样例,然后当然会有很多TLE,甚至还有一个WA,真是玄学。

#define eps 1e-4

int n,m,s[100005];
double sum[100005];

inline bool check(double x)
{
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+1.0*s[i]-x;
    double mn=1e9,now=-1e9;
    for (int i=m;i<=n;i++)
    {
        mn=min(mn,sum[i-m]);
        now=max(now,sum[i]-mn);
    }
    return (now>=0);
}

int main()
{
    n=read(); m=read();
    double l=1e9,r=0;
    for (int i=1;i<=n;i++) s[i]=read(),l=min(l,1.0*s[i]),r=max(r,1.0*s[i]);
    while (r-l>eps)
    {
        double mid=(l+r)/2;
        if (check(mid)) l=mid;
        else r=mid;
    }
    printf("%d",int(r*1000));
    return 0;
}

10013.曲线

三分 $x$ ,每次验证所有 $f_i(x)$ 的最大值。

还有我第一次直接输出 $x$ 都过了样例然后一交全WA,这样例简直害人不浅啊!

#define eps 1e-10

int t,n,m;
struct func{
    int a,b,c;
} s[100005];

inline double check(double x)
{
    double ans=-1e9;
    for (int i=1;i<=n;i++) ans=max(ans,(1.0*s[i].a*x*x+1.0*s[i].b*x+1.0*s[i].c));
    return ans;
}

int main()
{
    t=read();
    while (t--)
    {
        n=read();
        for (int i=1;i<=n;i++) s[i].a=read(),s[i].b=read(),s[i].c=read();
        double l=0,r=1000;
        while (r-l>eps)
        {
            double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
            if (check(r_mid)>check(l_mid)) r=r_mid;
            else l=l_mid;
        }
        printf("%.4f\n",check(l));
    }
    return 0;
}

10014.数列分段 II

还是二分答案,然后贪心验证。

这题我去年就写过了,这次就懒得写了,直接从洛谷复制过来,所以我也不知道我当时为什么要写递归版的二分。

int n,m,s[100005];

void search(int l,int r)
{
    if (l>r) 
    {
        printf("%d",l);
        return;
    }
    int mid=(l+r)/2;
    int sec=0,sum=0;
    for (int i=1;i<=n;i++)
    {
        if (sum+s[i]>mid)
        {
            sum=0;
            sec++;
        }
        sum+=s[i];
    }
    if (sec>=m) l=mid+1;
    else r=mid-1;
    search(l,r);
}

int main()
{
    n=read(); m=read();
    int l=0,r=0;
    for (int i=1;i<=n;i++) 
    {
        s[i]=read();
        l=max(l,s[i]);
        r+=s[i];
    }
    search(l,r);
    return 0;
}

10015.扩散

浙江10套里第九套原题

直接把所有点连起来跑Kruskal就行了,懒得写二分。

#define pr pair<int,int>
#define mp make_pair

struct point{
    int x,y;
} pt[55];
struct Edge{
    int st,ed,w;
} edge[2505];
int n,m,a,b,c,fa[55],cnt,ans;

inline void add(int u,int v,int w)
{
    edge[++cnt].st=u;
    edge[cnt].ed=v;
    edge[cnt].w=w;
}

inline void init()
{
    for (int i=1;i<=n;i++)
        fa[i]=i;
}

int getfa(int x)
{
    if (x==fa[x]) return fa[x];
    fa[x]=getfa(fa[x]);
    return fa[x];
}

inline bool merge(int x,int y)
{
    int gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    fa[gfx]=gfy;
    return 1;
}

inline bool cmp(Edge x,Edge y)
{
    return x.w<y.w;
}

inline void kruskal()
{
    for (int i=1;i<=cnt && n;i++)
    {
        int x=edge[i].st,y=edge[i].ed;
        if (merge(x,y))
        {
            n--;
            ans=max(ans,edge[i].w);
        }
    }
}

int main()
{
    n=read();
    init();
    for (int i=1;i<=n;i++) pt[i].x=read(),pt[i].y=read();
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            add(i,j,(abs(pt[i].x-pt[j].x)+abs(pt[i].y-pt[j].y)+1)>>1);
    sort(edge+1,edge+cnt+1,cmp);
    kruskal();
    printf("%d",ans);
    return 0;
}

10016.灯泡

设影子在墙上的部分的高度为 $x$ ,用相似可以推出影子总长度

$$L=D\times \dfrac {h-x}{H-x} +x$$

对其进行变形

$$L= \dfrac {D\times (H-h)}{x-H} + ( x - H ) + H + D$$

很显然这是一个对勾函数左侧,是个凸函数,所以三分即可。

#define eps 1e-5

int t;
double H,h,D;

inline double check(double x)
{
    return D*(h-x)/(H-x)+x;
}

int main()
{
    scanf("%d",&t);
    while (t--)
    {
        scanf("%lf%lf%lf",&H,&h,&D);
        double l=0,r=h;
        while (r-l>eps)
        {
            double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
            if (check(r_mid)<check(l_mid)) r=r_mid;
            else l=l_mid;
        }
        printf("%.3f\n",check(l));
    }
    return 0;
}

10017.传送带

我们假设在 $AB$ 段走到 $M$ 点,然后走到 $CD$ 段的 $N$ 点,那么可以得到时间为

$$T= \dfrac {AM}{P} + \dfrac {MN}{R} + \dfrac {ND}{Q}$$

很显然我们的目标就是找到合适的 $M$ 和 $N$ 让时间最小。

对于 $M$ ,如果我们知道 $k= \dfrac {AM}{AB}$ ,那么就可以确定 $M$ 的坐标为

$$M(Ax+(Bx-Ax)\times k,Ay+(By-Ay)\times k)$$

函数是个凹函数,证明,所以我们可以对 $k\in (0,1)$ 进行三分。

对于 $CD$ 段的 $N$ 也同理,进行两次三分后也就能确定答案了。

#define eps 1e-5

double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,p,q,r;

inline double get_dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double check2(double k1,double k2)
{
    double Mx=Ax+(Bx-Ax)*k1,My=Ay+(By-Ay)*k1,Nx=Cx+(Dx-Cx)*k2,Ny=Cy+(Dy-Cy)*k2;
    return get_dis(Ax,Ay,Mx,My)/p+get_dis(Mx,My,Nx,Ny)/r+get_dis(Nx,Ny,Dx,Dy)/q;
}

inline double check(double k)
{
    double l=0,r=1;
    while (r-l>eps)
    {
        double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
        if (check2(k,r_mid)>check2(k,l_mid)) r=r_mid;
        else l=l_mid;
    }
    return check2(k,l);
}

int main()
{
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&Ax,&Ay,&Bx,&By,&Cx,&Cy,&Dx,&Dy,&p,&q,&r);
    double l=0,r=1;
    while (r-l>eps)
    {
        double r_mid=(l+r)/2,l_mid=(l+r_mid)/2;
        if (check(r_mid)>check(l_mid)) r=r_mid;
        else l=l_mid;
    }
    printf("%.2f",check(l));
    return 0;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交或含有敏感词汇的评论将在审核后显示。