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

有哪个大佬给个思路?这个数据量有点恐怖。。。。二分没过。。。#C++工程师##字节跳动##Java工程师#
全部评论
#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); } }
点赞 回复
分享
发布于 2019-03-16 12:18
点赞 回复
分享
发布于 2019-03-16 11:58
秋招专场
校招火热招聘中
官网直投
二分过了90% 可能哪里写跪了 没细想了
点赞 回复
分享
发布于 2019-03-16 11:57
就是二分,精度在两位小数,r-l<0.001就行了
点赞 回复
分享
发布于 2019-03-16 12:01
精确到第三位就好
点赞 回复
分享
发布于 2019-03-16 12:03
先把第二行按从大到小排序,循环一个变量x,每次减0.01,计算第二行中每个元素除x可以得到几根绳子,将结果相加,当总和第一次大于等于m时,输出x
点赞 回复
分享
发布于 2019-03-16 12:26
 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直接过😃
点赞 回复
分享
发布于 2019-03-16 12:26
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
点赞 回复
分享
发布于 2019-03-16 16:22
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); } }
点赞 回复
分享
发布于 2019-03-18 16:28
把自己的解法捋了一遍,放到CSDN上了,欢迎探讨一下https://blog.csdn.net/weixin_43247186/article/details/88642032
点赞 回复
分享
发布于 2019-03-18 16:36

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务