paizaラーニング レベルアップ問題集 二分探索メニュー応用編 JavaScript 従業員

従業員 (paizaランク A 相当)

解答例

加える作業量で二分探索します。
範囲は0以上の整数、十分大きな10^14+1以下とします。
加える作業量をmid = Math.trunc((right + left) / 2)とします。
作業員一人の作業時間は、端数になった場合は、それぞれ 1 時間単位で切り上げなので、Math.ceil((B + mid)/A)で求まります。
全作業時間がK以下か調べ、探索を繰り返します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N, K] = lines[0].split(" ").map(Number);

//加える作業量で二分探索
let [left, right] = [0, 100000000000001];
while (right - left > 1) {
  const mid = Math.trunc((right + left) / 2);//仮の加える作業量
  
  let total = 0;//合計作業時間
  for (let i = 1; i <= N; i++) {
    const [A, B] = lines[i].split(" ").map(Number);
    //作業時間
    total += Math.ceil((B + mid) / A);//端数切り上げ
  }
  if (total <= K) {　//K時間以下なら、作業量は増やせる
    left = mid;
  } else { //K時間超えたら、作業時間は減らす
    right = mid;
  }
  
}
console.log(left);

解答例(pythonの場合参考)

探索を関数で定義して解きます。
x / y を切り上げた値を求める際には、(x + y - 1) / y を切り捨てた値を用いることができます。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N, K] = lines[0].split(" ").map(Number);
const AB = lines.slice(1).map(line => line.split(" ").map(Number));

//加える作業量で二分探索
//従業員の作業時間の合計が k 以下なら true, そうでないなら false を返す
const check = x => {
  // time : 作業量 x の時にかかる作業時間
  let time = 0;
  for (let i = 0; i < N; i++) {
    const task = x + AB[i][1];
    time += Math.floor((task + AB[i][0] - 1) / AB[i][0]);//切り上げ
  }
  if (time <= K) {
    return true;
  } else {
    return false;
  }
};

//leftは常に条件を満たす，rightは常に条件を満たさない
let [left, right] = [0, 10000000000001];
while (right - left > 1) {
  const mid = Math.trunc((right + left) / 2);//仮の加える作業量
  
  if (check(mid)) {　//K時間以下なら、作業量は増やせる
    left = mid;
  } else { //K時間超えたら、作業時間は減らす
    right = mid;
  }
  
}
console.log(left);