Minimum relative loss after buying chocolates

Array Binary Search Sorting Prefix Sum

46.6% acceptance

Mar 31, 2026

You are given an integer array prices, which shows the chocolate prices and a 2D integer array queries, where queries[i] = [ki, mi]. Alice and Bob went to buy some chocolates, and Alice suggested a way to pay for them, and Bob agreed. The terms for each query are as follows: If the price of a chocolate is less than or equal to ki, Bob pays for it. Otherwise, Bob pays ki of it, and Alice pays the rest. Bob wants to select exactly mi chocolates such that his relative loss is minimized, more formally, if, in total, Alice has paid ai and Bob has paid bi, Bob wants to minimize bi - ai. Return an integer array ans where ans[i] is Bob's minimum relative loss possible for queries[i].

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_relative_losses(prices: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> {
    let mut sorted = prices.clone();
    sorted.sort();
    let n = sorted.len();
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + sorted[i] as i64;
    }
    queries.iter().map(|q| {
      let k = q[0] as i64;
      let m = q[1] as usize;
      // items with price <= k: indices [0, cnt), cost = price, relative loss = price
      // items with price > k: indices [cnt, n), cost = k, alice pays p-k, relative loss = 2k-p
      let cnt = sorted.partition_point(|&x| x <= k as i32);
      // We pick m items total. 
      // From left group (price<=k): pick cheapest -> smallest loss = price
      // From right group (price>k): pick most expensive -> 2k-p is most negative
      // Binary search: how many from left (a) and right (m-a)?
      // a from left: take first a items, loss = prefix[a]
      // (m-a) from right: take last (m-a) items, loss = sum of (2k - p) for last (m-a) items
      // We want to find optimal a in [max(0, m-n+cnt), min(m, cnt)]
      let lo = if m > n - cnt { m - (n - cnt) } else { 0 };
      let hi = m.min(cnt);
      // Binary search: find largest a where taking one more from left is better
      // Left cost of a-th item (0-indexed): sorted[a]
      // Right cost of replacing: 2k - sorted[n - (m - a)] vs sorted[a]
      // We want sorted[a] <= 2k - sorted[n - (m-a)]
      let mut l = lo;
      let mut r = hi;
      while l < r {
        let mid = (l + r + 1) / 2;
        // Check if taking mid items from left is ok
        // The mid-th item from left (0-indexed: mid-1) has cost sorted[mid-1]
        // The item it replaces from right would be sorted[n - (m - mid) - 1] = sorted[n - m + mid - 1]
        // with cost 2k - sorted[n - m + mid - 1]
        // We want sorted[mid-1] <= 2k - sorted[n - m + mid - 1]
        if sorted[mid - 1] as i64 <= 2 * k - sorted[n - m + mid - 1] as i64 {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      let a = l;
      let b = m - a;
      // Cost from left: prefix[a]
      let left_cost = prefix[a];
      // Cost from right: sum of (2k - sorted[i]) for i in [n-b, n)
      // = 2k*b - (prefix[n] - prefix[n-b])
      let right_cost = 2 * k * b as i64 - (prefix[n] - prefix[n - b]);
      left_cost + right_cost
    }).collect()
  }
}