【华为面试题】：二分法

缺乏、安全感 2023-10-14 18:36 17阅读 0赞

### 题目内容 ###

![在这里插入图片描述][341237b17fa44da597c1fd9d2a03874c.png]

### 代码 ###

const readline = require("readline");
    
    const rl = readline.createInterface({
        
      input: process.stdin,
      output: process.stdout,
    });
    
    let inputLines = [];
    
    rl.on("line", (line) => {
        
      inputLines.push(line);
      if (inputLines.length === 2) {
        
        const [maxSum, bucketCount] = inputLines[0].split(" ").map(Number);
        const ballCounts = inputLines[1].split(" ").map(Number);
        computeBallRemovals(maxSum, ballCounts);
        rl.close();
      }
    });
    
    function computeBallRemovals(maxSum, ballCounts) {
        
      let totalBallCount = ballCounts.reduce((acc, val) => acc + val, 0);
      if (totalBallCount <= maxSum) {
        
        console.log("[]");
        return;
      }
    
      let left = 0;
      let right = Math.max(...ballCounts);
      let removals = new Array(ballCounts.length).fill(0);
    
      while (right - left > 1) {
        
        let mid = Math.floor((right + left) / 2);
        let sumAfterRemoval = 0;
    
        for (let i = 0; i < ballCounts.length; i++) {
        
          if (ballCounts[i] > mid) {
        
            sumAfterRemoval += mid;
          } else {
        
            sumAfterRemoval += ballCounts[i];
          }
        }
    
        if (sumAfterRemoval > maxSum) {
        
          right = mid;
        } else {
        
          left = mid;
          for (let i = 0; i < ballCounts.length; i++) {
        
            removals[i] = ballCounts[i] > mid ? ballCounts[i] - mid : 0;
          }
        }
      }
    
      console.log(removals.join(" "));
    }

[341237b17fa44da597c1fd9d2a03874c.png]: https://img-blog.csdnimg.cn/341237b17fa44da597c1fd9d2a03874c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 2022华为面试题

1、Java常用集合及特点？ List：ArrayList、LinkedList、Vector、Stack Set：LinkedSet、HashSet、TreeSet Que

亦凉/ 2024年03月22日 10:02/ 0 赞/ 31 阅读

相关 java华为面试题

JAVA方面 1 面向对象的特征有哪些方面 2 String是最基本的数据类型吗? 3 int 和 Integer 有什么区别 4 String 和S

柔光的暖阳◎/ 2024年03月16日 23:53/ 0 赞/ 56 阅读

相关【华为面试题】栈

![在这里插入图片描述][f9ae1d2d71784720a3d680bc6fced527.png] 思路首先，遍历输入的压缩字符串。三种情况： 1.遇到字符 ‘

阳光穿透心脏的1/2处/ 2023年10月14日 18:36/ 0 赞/ 24 阅读

相关【华为面试题】：二分法

题目内容 ![在这里插入图片描述][341237b17fa44da597c1fd9d2a03874c.png] 代码 const readline = r

缺乏、安全感/ 2023年10月14日 18:36/ 0 赞/ 18 阅读

相关 2023华为OD机试真题【最佳植树位置/二分法】

题目内容小明在直线的公路上种树，现在给定可以种树的坑位的数量和位置，以及需要种多少棵树苗，问树苗之间的最小间距是多少时，可以保证种的最均匀（两棵树苗之间的最小间距最大）

不念不忘少年蓝@/ 2023年10月12日 18:29/ 0 赞/ 66 阅读

相关华为电话面试题java_华为java面试题（含电话面试）

有一内存变量servicelist这是一个Arraylist,这个Arraylist已经保存在session“servicelis”中，现在需要有个页面把这个变量中的内容按列表

客官°小女子只卖身不卖艺/ 2022年11月08日 11:24/ 0 赞/ 194 阅读

相关华为python面试题

华为python面试题 2013-10-19 06:30:03阅读( 435 ) 1358人收藏本页标签：[Python面试题][Python] 有两个序列a,

￡神魔★判官ぃ/ 2022年09月18日 04:50/ 0 赞/ 179 阅读

相关算法笔记_面试题_17.二分法搜索_模板及示例

目录 1. 二分法搜索简介及模板例1. 在升序数组中，找第一次出现target对象的索引 2. 求开根号 sqrt(x) 例2. int sqrt( int x) 求

谁践踏了优雅/ 2022年08月28日 03:59/ 0 赞/ 96 阅读

相关华为python面试题

有两个序列a，b，大小都为n，序列元素的值任意整形数，无序；要求：通过交换a，b中的元素，使\[序列a元素的和\]与\[序列b元素的和\]之间的差最小。解题思路如下：

约定不等于承诺〃/ 2022年07月28日 10:59/ 0 赞/ 228 阅读

相关华为python面试题

有两个序列a，b，大小都为n，序列元素的值任意整形数，无序；要求：通过交换a，b中的元素，使\[序列a元素的和\]与\[序列b元素的和\]之间的差最小。解题思路如下：

ゞ浴缸里的玫瑰/ 2021年09月13日 20:46/ 0 赞/ 375 阅读