题目链接:http://bailian.openjudge.cn/p... 思路:         需要的等长网线数量C已知,要求尽可能长,那么我们可以列举所有网线可能的长度len(0,max] , 计算出每种长度下网线的数" />
  • 35648

    文章

  • 23

    评论

  • 20

    友链

  • 最近新加了很多技术文章,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

百练1064网线主管 含详细思路

欢迎来到阿八个人博客网站。本 阿八个人博客 网站提供最新的站长新闻,各种互联网资讯。 喜欢本站的朋友可以收藏本站,或者加QQ:我们大家一起来交流技术! URL链接:https://www.abboke.com/jsh/2019/0814/105824.html 1190000020061941nd">

题目链接:http://bailian.openjudge.cn/p...

思路:
        需要的等长网线数量C已知,要求尽可能长,那么我们可以列举所有网线可能的长度len(0,max] , 计算出每种长度下网线的数量,时间复杂度为 O(max*n)。为了加快计算,我们在列举网线长度时,采用二分法,假如在 len下算出的网线数量c < C, 那么就取一个更小的len尝试,反之取更大的len尝试,最优解L 满足 c(L) >= C, c(L+1) < C.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 0x3f3f3f3f
using namespace std;
int a[10010];
int b[10010];
int n,m;
int find(int x)
{
    int h=0;
    for(int i=1;i<=n;i++)
    {
        h=h+a[i]/x;
    } 
    return h;
}
int main()
{
 
    cin>>n>>m;
    b[1]=0;
    for(int i=1;i<=n;i++)
    {
        double w;
        cin>>w;
        a[i]=w*100;
        b[2]=max(b[2],a[i]);    
    } 
    int l=0,r=b[2];
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(mid==0)
        {
        printf("0.00");
        return 0;
        }
        if(find(mid)<m)
        {
            r=mid-1;    
        }
        else
        l=mid+1;
    }
    printf("%.2lf",(l-1)/100.0);
} 

效率:
提交人 班级 结果 内存 时间 代码长度 语言 提交时间


Accepted    672kB    49ms    575 B    G++    

相关文章

暂住......别动,不想说点什么吗?
  • 全部评论(0
    还没有评论,快来抢沙发吧!