首页 > 其他分享 >二分-剪绳子

二分-剪绳子

时间:2022-12-05 20:34:34浏览次数:40  
标签:二分 int double 绳子 mid ans 长度

有N根绳子,第i根绳子长度为Li,现在需要M根等长的绳子, 你可以对N根绳子进行任意裁剪(不能拼接), 请你帮忙计算出这M根绳子最长的长度是多少。

第一行包含2个正整数N、M,表示原始绳子的数量和需求绳子的数量。 第二行包含N个整数,其中第 i 个整数Li表示第 i 根绳子的长度。 已知:1≤N,M≤100000, 0<Li<10^9

输出一个数字,表示裁剪后最长的长度,保留两位小数。

样例输入

3 4

3 5 4

样例输出

2.50

代码实现

#include <iostream>
using namespace std;
const int M=1e5+10;
int a[M];
int n,m;
bool check(double x){
int ans=0;
for(int i=0;i<n;i++){
ans=ans+a[i]/x;
}
return ans>=m;
}
int main()
{

cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
double l=0,r=1e9;
while(r-l>1e-4){
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.2lf",l);
return 0;
}

标签:二分,int,double,绳子,mid,ans,长度
From: https://www.cnblogs.com/saulgoodman1/p/16953406.html

相关文章

  • c语言中-----二分法查找有序数组中某个数的下标
    intmain(){//二分法查找算法:查找(有序排列)数组中6对应的下标并输出intarr[]={1,2,3,4,5,6,7,8,9,10};//下标取中(第一个下标为0),进行比较判断......
  • leetcode 6256. 将节点分成尽可能多的组 二分图判定+bfs+并查集
    6256.将节点分成尽可能多的组难度困难7收藏分享切换为英文接收动态反馈给你一个正整数 n ,表示一个 无向 图中的节点数目,节点编号从 1 到 n 。同时给你一个......
  • 树上染色-题解(贪心+DP+二分)
    树的上色题意简述树上有两个黑点,在每个单位时间内,每个黑点可以把自己相邻的一个白点变为黑色,求把整棵树所有点变为黑色的最短时间。\(n\)个点,两个黑点分别为\(x,y\)。......
  • NO.704二分查找
    问题描述给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。示例1:输......
  • 数据结构 玩转数据结构 6-13 更多二分搜索树相关话题
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13478 1重点关注1.1待解决的问题(持续深进)求某个节点的floor和ceil求某个节点的......
  • golang二分查找算法
    一、条件:一组数据要进行二分查找,那么这个要查找的元素是有序,并且是连续存放(数组)。这样才可以进行二分查找。在数据库主键查找,二分查找算法是底层算法原理。二、下面用golang......
  • hdu棋盘游戏(二分图匹配)
    题目描述ProblemDescription小希和Gardon在玩一个游戏:对一个N*M的棋盘,在格子里放尽量多的一些国际象棋里面的“车”,并且使得他们不能互相攻击,这当然很简单,但是Gardon限......
  • 算法之二分查找
    1.二分查找:指的是通过找到中间值,用中间值和需要找的值作比较,在中间值的左右区间来判断需要寻找的值所在的位置。"""coding:utf-8@Software:PyCharm@Time:2022/12/116......
  • 二分图判定
    二分图的判定二分图的定义:若无向图\(G\)的所有节点可以划分为两个集合\(A,B\),若\(A,B\)均不为空且不存在一条边\((u,v)\)使得\(u,v\)属于同一集合,则称这个无向图为二分图......
  • wqs 二分
    更应该说是一种思想吧。我们希望知道恰好选择\(k\)个物品时的答案,但世界上哪来的那么多恰好呢。令\(f_x\)是恰好选择\(k\)个物品时的答案,那么点集\((x,f_x)\)常会......