求今天头条笔试最后一题解法

#include<iostream> #include<cmath> #include<stack> #include<algorithm> #include<cstring> #include<queue> using namespace std; const double eps = 1e-4; long long L[100005]; int n, m; bool fun(double len) { int sum = 0; for(int i = 0; i < n; i++) { sum += (int)(L[i] * 1.0 / len); if(sum >= m) { return true; } } return false; } bool cmp(long long a, long long b) { return a > b; } int main() { while(cin >> n >> m) { long long sum = 0; for(int i = 0; i < n; i++) { cin >> L[i]; sum += L[i]; } sort(L, L + n, cmp); double r = (double)sum / (m * 1.0); double l = 0; while(r - l >= eps) { double m = (l + r) / 2.0; if(fun(m)) { l = m; } else { r = m; } } printf("%.2lf\n", l); } }

二分过了90% 可能哪里写跪了 没细想了

就是二分，精度在两位小数，r-l<0.001就行了

精确到第三位就好

先把第二行按从大到小排序，循环一个变量x，每次减0.01，计算第二行中每个元素除x可以得到几根绳子，将结果相加，当总和第一次大于等于m时，输出x

 int n, m;     cin >> n >> m;     double l = 99999999, r = 0;     vector<double> all(n);     for (int i = 0; i < n; i++)     {         cin >> all[i];         l = min(l, all[i]);         r = max(r, all[i]);     }     l--, r++;     double mid;     double res = -1;     while (r - l > 1e-3)     {         mid = (l + r) / 2;         int cont = 0;         for (int i = 0; i < n; i++)             cont += all[i] / mid;         if (cont >= m)         {             l = mid;             res = mid;         }         else             r = mid;     }     cout << fixed << setprecision(2) << res << endl; 我也来贴一发 刚开始写的整数二分，跑了样例才改的浮点，所以可能有的地方有点奇怪 第一次1e-7精度上去T了，改1e-3直接过😃

js版 // arr为绳长数组， m为需要裁剪成的绳数 var longestRope = function(arr, m) { arr.sort((a, b) => { return a - b }) let lower = 0 let higher = arr[arr.length - 1] while((higher - lower) > 0.001) { let mid = (lower + higher) / 2 if (enough(arr, m, mid)) { lower = mid } else { higher = mid } } return toDecimal(lower, 2) } function enough(arr, m, ropeLength) { let sum = 0 let len = arr.length for(let i = 0; i < len; i ++) { sum += parseInt(arr[i] / ropeLength) if (sum >= m) { return true } } return false } // 保留n位小数，不足补0 function toDecimal(number, n) { number = number.toFixed(n) let index = number.indexOf('.') if (index < 0) { index = s.length number += '.' } while (number.length <= index + n) { number += '0' } return number } // 测试用例 let arr = [3, 4, 5] console.log(longestRope(arr, 4)) // 2.50

package spring; import java.util.*; public class Main5 { public static void main (String[] args){ Scanner sc = new Scanner(System.in); //准备工作 int n = sc.nextInt(); int m = sc.nextInt(); double[] arr = new double[n]; for(int i=0; i<n; i++) arr[i] = sc.nextDouble(); //从小到大排序 Arrays.sort(arr); //夹逼锁值，求出上界，再寻值 int poi = 0;//只需要找到有边界 for (int i=0; i < arr.length; i++){ int total = 1; for(int j=i+1; j < arr.length; j++){ total += arr[j]/arr[i]; if(total >= m) break; } if(total < m) { poi = i; break; } } //开始寻值(这里可以确定上下界限，然后采用折半查找) //下界的最小值为0.01，最大是arr[poi-1],取决于poi>0? arr[poi-1]:0.01 //上界是arr[poi] //折半查找的目的是找到一个值k， //使得k满足 以k为长度可以满足切割数大于等于m段，而以 k+0.01则不行 double rt = arr[poi]; double lf = poi > 0 ? arr[poi-1] : 0.01; double len = BinaryFind(arr, poi, m, lf, rt); System.out.println(String.format("%.2f", len)); } public static double BinaryFind (double[] arr, int poi,int m, double lf, double rt){ if (lf == rt) return lf; double mid = (lf + rt)/2; mid = Double.parseDouble(String.format("%.2f", mid));//保留小数点后两位 int m1 = 0; for (int i=poi; i < arr.length; i++){ m1 += arr[i]/mid; if (m1 >m) break; } int m2 = 0; for (int i=poi; i < arr.length; i++){ m2 += arr[i]/(mid+0.01); if (m2 > m) break; } if(m1 >= m && m2 < m) return mid;//找到最优解 if (m2 >= m) { lf = Double.parseDouble(String.format("%.2f", mid+0.01)); return BinaryFind(arr, poi, m, lf, rt); } return BinaryFind(arr, poi, m, lf, mid); } }

把自己的解法捋了一遍，放到CSDN上了，欢迎探讨一下https://blog.csdn.net/weixin_43247186/article/details/88642032