美文网首页
二分法,三分法的应用

二分法,三分法的应用

作者: 碧影江白 | 来源:发表于2016-09-15 17:32 被阅读142次

在了解了关于二分法,三分法的相关原理之后,需要进一步熟练运用,下面两道题:

二分法应用:
HDU Cable master:
http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=4&sectionid=1&problemid=10
题意:n个木棒,分成m个大小相等的小木棒,问分割后最大的长度是多少?
如:2.00 , 3.00 , 4.00长度的三根木棒,分成2个,最大的应该是3,而不是4。
开始二分:由于每根的大小必定大于1,那么长度应该在1和最长的木棒长度之间,由此二分,总的木棒可以分成长度为mid的木棒数量大于m,那么,可以使mid增加,即left=mid+1,否则使mid减小,right=mid-1,直到left=mid。
代码如下:

#include<iostream>
using namespace std;

int main()
{
    double temp,eps=1e-7;
    int i,sum,max,low,high,mid,ans,n,k,s[10001];
    while(cin>>n>>k && (n||k))
    {
        sum=max=0;
        for(i=0;i<n;i++)
        {
            cin>>temp;
            s[i]=(int)((temp+eps)*100);
            if(max<s[i])
                max=s[i];
        }

        ans=0;
        low=1;
        high=max;
        while(high>=low)
        {
            sum=0;
            mid=(low+high)/2;
            for(i=0;i<n;i++)
                sum+=s[i]/mid;
            if(sum>=k)
            {
                low=mid+1;
                if(ans<mid)
                    ans=mid;
            }
            else
                high=mid-1;
        }
        printf("%.2lf\n",ans*0.01);
    }
}

三分法应用:
HDU Line belt
http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=4&sectionid=1&problemid=9
题意:过河,两个平行线AB,CD,想要从A到达D,已知在AB,CD和其他地方的速度,求解所用的最短时间。
三分思维:三分法可以得到两段的最短时间,如:

假设已知拐点a,c,从ac中选择一个b点,使得在ab,bc上用的总时间为最少,那么,可以解答出相关的b点,而a点是不确定的,可以在三分算法中使用三分算法,规划成两个以上的结构,具体实现看代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define eps 1e-8
using namespace std;
int sgn(double n){
    if(fabs(n)<eps)return 0;
    else if(n<0)return -1;
    return 1;
}
struct point{
    double x,y;
}A,B,C,D;
double p,q,r;
double dist(point p1,point p2){
    return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
double Three2(point a){
    point left=C,right=D;
    point mid,mmid;
    double t1,t2;
    int size=100;
    while(size--){
        mid.x=(left.x+right.x)/2.0;
        mid.y=(left.y+right.y)/2.0;
        mmid.x=(mid.x+right.x)/2.0;
        mmid.y=(mid.y+right.y)/2.0;
        t1=dist(a,mid)/r+dist(mid,D)/q;
        t2=dist(a,mmid)/r+dist(mmid,D)/q;
        if(t1>t2)
            left=mid;
        else 
            right=mmid;
    }
    return t1;
}
double Three1(){
    point left=A,right=B;
    point mid,mmid;
    double t1,t2;
    int size=100;
    while(size--){
        mid.x=(left.x+right.x)/2.0;
        mid.y=(left.y+right.y)/2.0;
        mmid.x=(mid.x+right.x)/2.0;
        mmid.y=(mid.y+right.y)/2.0;
        t1=dist(A,mid)/p+Three2(mid);
        t2=dist(A,mmid)/p+Three2(mmid);
        if(t1>t2)
            left=mid;
        else
            right=mmid;
    }
    return t1;
} 
int main()
{
    int t,i,j,k;
    scanf("%d",&t);
    while(t--){
        scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
        scanf("%lf%lf%lf%lf",&C.x,&C.y,&D.x,&D.y);
        scanf("%lf%lf%lf",&p,&q,&r);
        printf("%.2lf\n",Three1());
    }
    return 0;
}

相关文章

  • 二分法,三分法的应用

    在了解了关于二分法,三分法的相关原理之后,需要进一步熟练运用,下面两道题: 二分法应用:HDU Cable mas...

  • 谈摄影构图中的平衡

    摄影构图有很多种方法,二分法,三分法,对称法,引导线法,黄金分割法等等不一而足,但是初学者学会了,也应用在自己的照...

  • 星座简谈

    十二星座,起源于西方,早在隋朝便已传进中国。 十二星座分类:二分法、三分法、四分法 ...

  • 【思维导图实战派】刻意练习之“遇见成长的自己”计划11/300:

    昨天的感悟是对一分法,二分法,三分法的思考: 一分法,说什么我都信或者说什么我都不信。 二分法:是说什么我会通过思...

  • 五场误会03

    原则二——会造成分化效果的话不说 在本章一开头的故事当中,多半出问题的原因,都在于说话的人用了“二分法”或“三分法...

  • 『贰』 伪文艺者的构图。

    构图第一要素 不要太满不要太满不要太满。 然后呐,对角线、黄金分割、三分法、二分法、螺旋式。实在不好把握...

  • 活学活用之——投资三分法的灵活运用

    上一篇科普为大家介绍了投资三分法的基本概念和简单应用,其实,投资三分法并不是一个具体的方法,而是一种投资思想,因此...

  • 让照片更漂亮的三分构图法

    如果你还不知道三分法则,那么一定会惊讶于应用这个法则的照片看起来会比不遵守法则的照片好出多少。 三分法则是一个简单...

  • 二分法总结

    二分法总结 二分法貌似简单,实则很多细节,需要多加注意才能写对。 应用 1 在单调递增数组中确认是否有指定targ...

  • java 快速排序的思想及解释说明

    快速排序在应用上很广泛,大家有知道二分法,二分法在排好序的数组中查找数据是最快的 快速排序是在无序的数组中排序、查...

网友评论

      本文标题:二分法,三分法的应用

      本文链接:https://www.haomeiwen.com/subject/jrubettx.html