【POJ - 1064】Cable master（二分）

佚名 5年前 (2019-08-03) 算法 2255人围观抢沙发百度已收录

Cable master

直接上中文了

Descriptions

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入2个数 N K

n条绳子要分成大于等于k段

求每段最长多长呢？并且每段不能小于1cm

必须以厘米精度写入数字，小数点后正好是两位数。
如果无法切割所请求的每个长度至少为1厘米的件数，则输出文件必须包含单个数字“0.00”（不带引号）。

多组文件输入

Sample Input

Sample Output

2.00

题目链接

https://vjudge.net/problem/POJ-1064

这个输出是个坑点，不能直接用double，然后 printf("%.2f\n"）这会自动四舍五入，是错误的，我看其他大佬的方法是，输入时先*100输出的时候/100就能解决这个输出问题

其他的没什么，就是二分，不懂的再看看代码吧

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 10000+5
using namespace std;
int l,r;//左，右
int N,K;
int main()
{
    while(cin>>N>>K)
    {
        int len[Maxn];//绳子
        for(int i=0; i<N; i++)
        {
            double t;
            cin>>t;
            len[i]=t*100.0;
        }
        sort(len,len+N);//排序，直接找最大值
        l=1,r=len[N-1];
        int ans=0;//答案
        while(l<=r)
        {
            int mid=(l+r)/2;
            int cnt=0;//计数器，是否大于等于K
            for(int i=0; i<N; i++)
                cnt+=len[i]/mid;
            if(cnt>=K)
            {
                l=mid+1;
                ans=max(ans,mid);//找最大值
            }
            else
                r=mid-1;
        }
        printf("%.2f\n",(double)ans/100.0);
    }
    return 0;
}