1648-sell-diminishing-valued-colored-balls.js

/**
 * @param {number[]} inventory
 * @param {number} orders
 * @return {number}
 */
const maxProfit = function(inventory, orders) {
  const bigIntMax = (...args) => args.reduce((m, e) => e > m ? e : m);
  inventory = inventory.map(e => BigInt(e))
  orders = BigInt(orders)
  let l = 0n, r = bigIntMax(...inventory)
  while(l < r) {
    const mid = l + (r - l) / 2n
    if(valid(mid)) l = mid + 1n
    else r = mid
  }
  
  // console.log(l)
  const mod = BigInt(1e9 + 7)
  let t = l, res = 0n, cnt = 0n
  for(const e of inventory) {
    if(e <= t) continue
    cnt += e - t
    res = (res + (t + 1n + e) * (e - t) / 2n) % mod
  }
  
  res = (res + (orders - cnt) * t) % mod
  
  return res
  
  function valid(mid) {
    let res = 0n
    for(const e of inventory) {
      if(e > mid) res += e - mid
    }
    return res > orders
  }
};

// another

/**
 * @param {number[]} inventory
 * @param {number} orders
 * @return {number}
 */
function maxProfit(inventory, orders) {
  inventory.sort((a, b) => a - b)
  inventory = inventory.map(e => BigInt(e))
  let ans = 0n, n = inventory.length - 1, count = 1n
  const mod = BigInt(10 ** 9 + 7)
  orders = BigInt(orders)
  while(orders > 0n) {
    if(n > 0 && inventory[n] > inventory[n - 1] && orders >= count * (inventory[n] - inventory[n - 1])) {
      ans += count * sum(inventory[n - 1], inventory[n])
      orders -= count * (inventory[n] - inventory[n - 1])
    } else if(n === 0 || inventory[n] > inventory[n - 1]) {
      const num = orders / count
      ans += count * sum(inventory[n] - num, inventory[n])
      const remain = orders % count
      ans += remain * (inventory[n] - num)
      orders = 0n
    }
    ans %= mod
    n--
    count++
  }
  return ans
}

function sum(lo, hi) {
  return (hi - lo) * (lo + hi + 1n) / 2n
}

// another

/**
 * @param {number[]} inventory
 * @param {number} orders
 * @return {number}
 */
const maxProfit = function (inventory, orders) {
  let Max = 1e9 + 7,
    Min = 0
  let mod = BigInt(1e9 + 7)
  while (Max > Min + 1) {
    let tot = 0
    let mid = ((Max + Min) >> 1)
    for (let it of inventory) {
      if (it > mid) tot += it - mid
    }
    if (tot > orders) Min = mid
    else Max = mid
  }
  let sum = BigInt(0)
  Max = BigInt(Max)
  orders = BigInt(orders)
  for (let it of inventory) {
    it = BigInt(it)
    if (it > Max) {
      sum += ((it + Max + BigInt(1)) * (it - Max)) / BigInt(2)
      orders -= it - Max
    }
  }
  sum += orders * Max
  
  return sum % mod
}

// another

/**
 * @param {number[]} inventory
 * @param {number} orders
 * @return {number}
 */
var maxProfit = function(inventory, orders) {
    inventory.sort((a, b) => b - a)
    const mod = BigInt(1e9 + 7), n = BigInt(inventory.length)
    inventory = inventory.map(e => BigInt(e))
    orders = BigInt(orders)
    let cur = BigInt(inventory[0]), res = 0n, i = 0n
    const min = (a, b) => a > b ? b : a
    while(orders) {
      while(i < n && inventory[i] === cur) i++
      let next = i === n ? 0n : inventory[i]
      let h = cur - next, r = 0n, cnt = min(orders, i * h)
      if (orders < i * h) {
        h = orders / i
        r = orders % i
      }
      let val = cur - h
      res = (res + (cur + val + 1n) * h / 2n * i + val * r) % mod
      orders -= cnt
      cur = next
    }

    return res
};

// another

/**
 * @param {number[]} inventory
 * @param {number} orders
 * @return {number}
 */
const maxProfit = function (inventory, orders) {
  inventory.sort((a, b) => b - a)
  const mod = BigInt(1e9 + 7),
    n = BigInt(inventory.length)
  inventory = inventory.map((e) => BigInt(e))
  orders = BigInt(orders)
  let cur = BigInt(inventory[0]),
    res = 0n,
    i = 0n
  const min = (a, b) => (a > b ? b : a)
  while (orders) {
    while (i < n && inventory[i] === cur) i++
    let next = i === n ? 0n : inventory[i]
    let h = cur - next,
      r = 0n,
      cnt = min(orders, i * h)
    if (orders < i * h) {
      h = orders / i
      r = orders % i
    }
    let val = cur - h
    res = (res + (((cur + val + 1n) * h) / 2n) * i + val * r) % mod
    orders -= cnt
    cur = next
  }

  return res
}