C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
constexpr int N = 1e+6;
int arr[N]; //题目说明的是整数,但这里其实为double类型也能AC
int n, m;
bool check(double mid)
{
int cnt = 0;
for(int i = 0 ; i < n ; i++)
{
cnt += arr[i] / mid; // int / double --> 结果double运算的结果,然后结果给int类型运算进行下取整截断
}
return cnt >= m; //当要求的绳子的长度为mid时,此时最多能裁剪出cnt根,与要求的m根比较。
}
int main()
{
cin >> n >> m ;
for(int i = 0; i < n ; i++) cin >> arr[i] ;
double l = 0, r = 1e+9;
double mid ;
for(int i = 0; i < 100; i++) // 由于是浮点数二分,因为绳子的长度二分就是浮点形式带小数的,故这里二分的退出条件 1 . while(r - l > 1e-x) 这种, 或者是直接无脑的for循环100次
{
mid = (l+r) / 2;
if(check(mid)) l = mid; //若check为真,说明此时的mid偏小了,故答案应该在右边 l = mid , r 的区间里面
else r = mid;
}
printf("%.2lf\n",l); //答案最后要求保留 2 位
// cout << l << endl;
}
分析思路
首先如果从题目的意思直接求解,不知如何下手,这里真的刚开始没有想到二分去
题目说明绳子不能拼接 –》 这个条件说明了每根绳子的剪裁是独立的
将N根绳子裁剪成 M 根等长的绳子
这里的思路是假设要裁剪出长度为x的绳子,那么N根绳子最多可以裁剪出多少根这个问题
这个问题就简单多了,由于每根绳子是独立的,故其中一根绳子能裁剪出x长度的绳子的条数为 num = l / x; l 为 该绳子的总长度
num 为其运算的下取整的结果。 故对于其他绳子同样采用相同的方法求出, 最后求和 sum = num1 + num2 + num3 + .... 得到这些
绳子最多能裁剪出多少条绳子的问题。这里作为二分的条件,如果最多裁剪出的条数大于要求的M,则表示这个x小了,可以裁剪得更长导致
裁剪出的条数减少,以此类推,当不断增大x的时候,此时sum 趋近于 M。 —》 故这里就是二分的条件思路判断