2819. Minimum Relative Loss After Buying Chocolates

• Time: $O(\texttt{sort} + q\log n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  vector<long long> minimumRelativeLosses(vector<int>& prices,
                                          vector<vector<int>>& queries) {
    const int n = prices.size();
    vector<long long> ans;
    vector<long long> prefix{0};

    sort(prices.begin(), prices.end());

    for (const int price : prices)
      prefix.push_back(prefix.back() + price);

    for (const vector<int>& query : queries) {
      const int k = query[0];
      const int m = query[1];
      const int countFront = getCountFront(k, m, prices, prefix);
      const int countBack = m - countFront;
      ans.push_back(getRelativeLoss(countFront, countBack, k, prefix));
    }

    return ans;
  }

 private:
  // Returns the `countFront` for query (k, m) s.t. picking the first
  // `countFront` and the last `m - countFront` chocolates is optimal.
  //
  // Define loss[i] := the relative loss of picking `prices[i]`.
  // (1) For prices[i] <= k, Bob pays prices[i] while Alice pays 0.
  //     Thus, loss[i] = prices[i] - 0 = prices[i].
  // (2) For prices[i] > k, Bob pays k while Alice pays prices[i] - k.
  //     Thus, loss[i] = k - (prices[i] - k) = 2 * k - prices[i].
  // By observation, we deduce that it is always better to pick from the front
  // or the back since loss[i] is increasing for (1) and is decreasing for (2).
  //
  // Assume that picking `left` chocolates from the left and `right = m - left`
  // chocolates from the right is optimal. Therefore, we are selecting
  // chocolates from `prices[0..left - 1]` and `prices[n - right..n - 1]`.
  //
  // To determine the optimal `left` in each iteration, we simply compare
  // `loss[left]` with `loss[n - right]`; if `loss[left] < loss[n - right]`,
  // it's worth increasing `left`.
  int getCountFront(int k, int m, const vector<int>& prices,
                    const vector<long long>& prefix) {
    const int n = prices.size();
    const int countNoGreaterThanK =
        upper_bound(prices.begin(), prices.end(), k) - prices.begin();
    int l = 0;
    int r = min(countNoGreaterThanK, m);

    while (l < r) {
      const int mid = (l + r) / 2;
      const int right = m - mid;
      // Picking prices[mid] is better than picking prices[n - right].
      if (prices[mid] < 2LL * k - prices[n - right])
        l = mid + 1;
      else
        r = mid;
    }

    return l;
  }

  // Returns the relative loss of picking `countFront` and `countBack`
  // chocolates.
  long long getRelativeLoss(int countFront, int countBack, int k,
                            const vector<long long>& prefix) {
    const long long lossFront = prefix[countFront];
    const long long lossBack =
        2LL * k * countBack -
        (prefix.back() - prefix[prefix.size() - 1 - countBack]);
    return lossFront + lossBack;
  }
};

class Solution {
  long[] minimumRelativeLosses(int[] prices, int[][] queries) {
    final int n = prices.length;
    long[] ans = new long[queries.length];
    long[] prefix = new long[prices.length + 1];

    Arrays.sort(prices);

    for (int i = 0; i < prices.length; ++i)
      prefix[i + 1] = prefix[i] + prices[i];

    for (int i = 0; i < queries.length; ++i) {
      final int k = queries[i][0];
      final int m = queries[i][1];
      final int countFront = getCountFront(k, m, prices, prefix);
      final int countBack = m - countFront;
      ans[i] = getRelativeLoss(countFront, countBack, k, prefix);
    }

    return ans;
  }

  // Returns the `countFront` for query (k, m) s.t. picking the first
  // `countFront` and the last `m - countFront` chocolates is optimal.
  //
  // Define loss[i] := the relative loss of picking `prices[i]`.
  // (1) For prices[i] <= k, Bob pays prices[i] while Alice pays 0.
  //     Thus, loss[i] = prices[i] - 0 = prices[i].
  // (2) For prices[i] > k, Bob pays k while Alice pays prices[i] - k.
  //     Thus, loss[i] = k - (prices[i] - k) = 2 * k - prices[i].
  // By observation, we deduce that it is always better to pick from the front
  // or the back since loss[i] is increasing for (1) and is decreasing for (2).
  //
  // Assume that picking `left` chocolates from the left and `right = m - left`
  // chocolates from the right is optimal. Therefore, we are selecting
  // chocolates from `prices[0..left - 1]` and `prices[n - right..n - 1]`.
  //
  // To determine the optimal `left` in each iteration, we simply compare
  // `loss[left]` with `loss[n - right]`; if `loss[left] < loss[n - right]`,
  // it's worth increasing `left`.
  private int getCountFront(int k, int m, int[] prices, long[] prefix) {
    final int n = prices.length;
    final int countNoGreaterThanK = firstGreater(prices, k);
    int l = 0;
    int r = Math.min(countNoGreaterThanK, m);

    while (l < r) {
      final int mid = (l + r) / 2;
      final int right = m - mid;
      // Picking prices[mid] is better than picking prices[n - right].
      if (prices[mid] < 2L * k - prices[n - right])
        l = mid + 1;
      else
        r = mid;
    }

    return l;
  }

  private int firstGreater(int[] A, int val) {
    final int i = Arrays.binarySearch(A, val + 1);
    return i < 0 ? -(i + 1) : i;
  }

  // Returns the relative loss of picking `countFront` and `countBack`
  // chocolates.
  private long getRelativeLoss(int countFront, int countBack, int k, long[] prefix) {
    final int n = prefix.length - 1;
    final long lossFront = prefix[countFront];
    final long lossBack = 2L * k * countBack - (prefix[n] - prefix[n - countBack]);
    return lossFront + lossBack;
  }
}

class Solution:
  def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:
    ans = []

    prices.sort()

    prefix = [0] + list(itertools.accumulate(prices))

    for k, m in queries:
      countFront = self._getCountFront(k, m, prices, prefix)
      countBack = m - countFront
      ans.append(self._getRelativeLoss(countFront, countBack, k, prefix))

    return ans

  def _getCountFront(self, k: int, m: int, prices: List[int], prefix: List[int]) -> int:
    """Returns the `countFront` for query (k, m).

    Returns the `countFront` for query (k, m) s.t. picking the first
    `countFront` and the last `m - countFront` chocolates is optimal.

    Define loss[i] := the relative loss of picking `prices[i]`.
    (1) For prices[i] <= k, Bob pays prices[i] while Alice pays 0.
        Thus, loss[i] = prices[i] - 0 = prices[i].
    (2) For prices[i] > k, Bob pays k while Alice pays prices[i] - k.
        Thus, loss[i] = k - (prices[i] - k) = 2 * k - prices[i].
    By observation, we deduce that it is always better to pick from the front
    or the back since loss[i] is increasing for (1) and is decreasing for (2).

    Assume that picking `left` chocolates from the left and `right = m - left`
    chocolates from the right is optimal. Therefore, we are selecting
    chocolates from `prices[0..left - 1]` and `prices[n - right..n - 1]`.

    To determine the optimal `left` in each iteration, we simply compare
    `loss[left]` with `loss[n - right]` if `loss[left] < loss[n - right]`,
    it's worth increasing `left`.
    """
    n = len(prices)
    countNoGreaterThanK = bisect.bisect_right(prices, k)
    l = 0
    r = min(countNoGreaterThanK, m)

    while l < r:
      mid = (l + r) // 2
      right = m - mid
      # Picking prices[mid] is better than picking prices[n - right].
      if prices[mid] < 2 * k - prices[n - right]:
        l = mid + 1
      else:
        r = mid

    return l

  def _getRelativeLoss(self, countFront: int, countBack: int, k: int, prefix: List[int]) -> int:
    """Returns the relative loss of picking `countFront` and `countBack` chocolates."""
    lossFront = prefix[countFront]
    lossBack = 2 * k * countBack - (prefix[-1] - prefix[-countBack - 1])
    return lossFront + lossBack