【杭电1551】Cable master

柔情只为你懂 2022-09-24 06:15 154阅读 0赞

![这里写图片描述][20160726212958369]  
![这里写图片描述][20160726213007260]

题意：把4段网线分成11段每段至多多长。  
现在总结一下二分的思想和步骤吧：  
1.找到二分标准，就是对什么进行二分  
2.找到两个临界点  
3.判断mid时，是否满足条件，然后视情况更新l和r的值  
4.我认为最重要的是while（）括号内的条件选择，特别是对这种卡精度的题。

#include<stdio.h>
    #include<math.h>
    const int MAXN = 1*1e4+10;
    double a[MAXN];
    int n,t;
    bool judge(double mid) {
        int cnt=0;
        for(int l=0; l<n; l++) {
            cnt+=(a[l]/mid);
        }
        return cnt>=t;
    }
    int main() {
        while(scanf("%d%d",&n,&t),n||t) {
            double sum=0.0;
            for(int l=0; l<n; l++) {
                scanf("%lf",&a[l]);
                sum+=a[l];
            }
            double l=0,r=sum/t;
            double mid;
            while(fabs(l-r)>1e-5) {
                mid=(l+r)/2;
                if(judge(mid)) {
                    l=mid;
                } else {
                    r=mid;
                }
            }
            printf("%.2lf\n",mid);
        }
        return 0;
    }

[http://acm.hdu.edu.cn/showproblem.php?pid=1551][http_acm.hdu.edu.cn_showproblem.php_pid_1551]

[20160726212958369]: /images/20220719/a1ad39ea73984b778b44fb0defb3b827.png
[20160726213007260]: /images/20220719/28e46b8582cb44868ba635164d0c9b88.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1551]: http://acm.hdu.edu.cn/showproblem.php?pid=1551

发表评论取消回复

表情：

评论列表（有 0 条评论，154人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj1064（二分）Cable master

//二分判断 /假定一个解并判断是否可行题意：有n条绳子，长度分别为L[i]。如果从他们中切割出k条长度相同的绳子的话，这k条绳子每条最长能有多长

女爷i/ 2024年02月18日 14:02/ 0 赞/ 52 阅读

相关【杭电1551】Cable master

![这里写图片描述][20160726212958369] ![这里写图片描述][20160726213007260] 题意：把4段网线分成11段每段至多多长。现在

柔情只为你懂/ 2022年09月24日 06:15/ 0 赞/ 155 阅读

相关杭电1061

Rightmost Digit Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

布满荆棘的人生/ 2022年09月17日 05:27/ 0 赞/ 327 阅读

相关 Cable master POJ - 1064 题解

题目链接 https://vjudge.net/problem/POJ-1064 当然我是在Virtual Judge上面写的，可以直接去POJ去提交。这个题目感觉

冷不防/ 2022年09月02日 04:16/ 0 赞/ 197 阅读

相关 Cable master--hdu1551(二分法)

Cable master Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/O

Dear 丶/ 2022年08月04日 08:55/ 0 赞/ 54 阅读

相关杭电1026

Ignatius and the Princess I Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 6553

快来打我*/ 2022年06月04日 05:53/ 0 赞/ 341 阅读

相关 Cable master

Cable master <table style="max-width:100%;border-spacing:0px;width:1615px;margin-bott

Bertha 。/ 2022年05月30日 02:53/ 0 赞/ 201 阅读

相关杭电2078

说实话，此题是一道有严重bug的问题，对于xhd没晚能复习的科目数m根本就没用上！！！哎不管那么些了，反正ac了！呵呵！此题这样想xhd得复习效率是前一课程和后一课程复习效率差

╰+攻爆jí腚メ/ 2021年12月01日 22:38/ 0 赞/ 394 阅读

相关 POJ 1064 Cable master（二分答案）

嗯... 题目链接：[http://poj.org/problem?id=1064][http_poj.org_problem_id_1064] 其实

骑猪看日落/ 2021年10月23日 17:56/ 0 赞/ 275 阅读

相关 Cable master POJ - 1064 (二分精度)

[题目][Link 1] 思路：二分每条绳子的长度，循环100次即可。判断条件：每一段向下取整求最大可以裁剪的数量，如果所有数量大于等于k则满足l=mid,小于则

柔光的暖阳◎/ 2021年07月16日 15:34/ 0 赞/ 338 阅读