Tap here to switch tabs
Problem
Submissions

Problem: Minimum Relative Loss After Buying Chocolates

Minimum Relative Loss After Buying Chocolates asks you to select the requested number of chocolates per query and minimize Bob's payment minus Alice's, with each cost split at the query's threshold.

Statement

You are given an integer array prices of length n, representing the prices of various chocolates, and a 2extD2 ext{D} integer array queries, where queries[i] =[ki,mi]= [k_i, m_i].

For each query, Bob must choose exactly mim_i chocolates from prices. Alice and Bob share the cost of each selected chocolate with price pp as follows:

  • If p≤kip \leq k_i, Bob pays pp and Alice pays 00.

  • If p>kip > k_i, Bob pays kik_i and Alice pays p−kip - k_i.

The relative loss of a purchase is defined as the total amount Bob pays minus the total amount Alice pays across all mim_i selected chocolates.

Return an array of integers representing the minimum possible relative loss Bob can achieve for each query.

Constraints:

  • 1≤1 \leq prices.length =n≤105= n \leq 10^5

  • 1≤1 \leq prices[i] ≤109\leq 10^9

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • queries[i].length =2= 2

  • 1≤ki≤1091 \leq k_i \leq 10^9

  • 1≤mi≤n1 \leq m_i \leq n

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Relative Loss After Buying Chocolates

Minimum Relative Loss After Buying Chocolates asks you to select the requested number of chocolates per query and minimize Bob's payment minus Alice's, with each cost split at the query's threshold.

Statement

You are given an integer array prices of length n, representing the prices of various chocolates, and a 2extD2 ext{D} integer array queries, where queries[i] =[ki,mi]= [k_i, m_i].

For each query, Bob must choose exactly mim_i chocolates from prices. Alice and Bob share the cost of each selected chocolate with price pp as follows:

  • If p≤kip \leq k_i, Bob pays pp and Alice pays 00.

  • If p>kip > k_i, Bob pays kik_i and Alice pays p−kip - k_i.

The relative loss of a purchase is defined as the total amount Bob pays minus the total amount Alice pays across all mim_i selected chocolates.

Return an array of integers representing the minimum possible relative loss Bob can achieve for each query.

Constraints:

  • 1≤1 \leq prices.length =n≤105= n \leq 10^5

  • 1≤1 \leq prices[i] ≤109\leq 10^9

  • 1≤1 \leq queries.length ≤105\leq 10^5

  • queries[i].length =2= 2

  • 1≤ki≤1091 \leq k_i \leq 10^9

  • 1≤mi≤n1 \leq m_i \leq n