classSolution{public:vector<longlong>minimumRelativeLosses(vector<int>&prices,vector<vector<int>>&queries){constintn=prices.size();vector<longlong>ans;vector<longlong>prefix{0};ranges::sort(prices);for(constintprice:prices)prefix.push_back(prefix.back()+price);for(constvector<int>&query:queries){constintk=query[0];constintm=query[1];constintcountFront=getCountFront(k,m,prices);constintcountBack=m-countFront;ans.push_back(getRelativeLoss(countFront,countBack,k,prefix));}returnans;}private:// Returns `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`.intgetCountFront(intk,intm,constvector<int>&prices){constintn=prices.size();constintcountNoGreaterThanK=ranges::upper_bound(prices,k)-prices.begin();intl=0;intr=min(countNoGreaterThanK,m);while(l<r){constintmid=(l+r)/2;constintright=m-mid;// Picking prices[mid] is better than picking prices[n - right].if(prices[mid]<2L*k-prices[n-right])l=mid+1;elser=mid;}returnl;}// Returns the relative loss of picking `countFront` and `countBack`// chocolates.longgetRelativeLoss(intcountFront,intcountBack,intk,constvector<longlong>&prefix){constlonglossFront=prefix[countFront];constlonglossBack=2L*k*countBack-(prefix.back()-prefix[prefix.size()-1-countBack]);returnlossFront+lossBack;}};
classSolution{long[]minimumRelativeLosses(int[]prices,int[][]queries){finalintn=prices.length;long[]ans=newlong[queries.length];long[]prefix=newlong[prices.length+1];Arrays.sort(prices);for(inti=0;i<prices.length;++i)prefix[i+1]=prefix[i]+prices[i];for(inti=0;i<queries.length;++i){finalintk=queries[i][0];finalintm=queries[i][1];finalintcountFront=getCountFront(k,m,prices);finalintcountBack=m-countFront;ans[i]=getRelativeLoss(countFront,countBack,k,prefix);}returnans;}// Returns `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`.privateintgetCountFront(intk,intm,int[]prices){finalintn=prices.length;finalintcountNoGreaterThanK=firstGreater(prices,k);intl=0;intr=Math.min(countNoGreaterThanK,m);while(l<r){finalintmid=(l+r)/2;finalintright=m-mid;// Picking prices[mid] is better than picking prices[n - right].if(prices[mid]<2L*k-prices[n-right])l=mid+1;elser=mid;}returnl;}privateintfirstGreater(int[]A,inttarget){finalinti=Arrays.binarySearch(A,target+1);returni<0?-i-1:i;}// Returns the relative loss of picking `countFront` and `countBack`// chocolates.privatelonggetRelativeLoss(intcountFront,intcountBack,intk,long[]prefix){finalintn=prefix.length-1;finallonglossFront=prefix[countFront];finallonglossBack=2L*k*countBack-(prefix[n]-prefix[n-countBack]);returnlossFront+lossBack;}}
classSolution:defminimumRelativeLosses(self,prices:list[int],queries:list[list[int]],)->list[int]:ans=[]prices.sort()prefix=list(itertools.accumulate(prices,initial=0))fork,minqueries:countFront=self._getCountFront(k,m,prices)countBack=m-countFrontans.append(self._getRelativeLoss(countFront,countBack,k,prefix))returnansdef_getCountFront(self,k:int,m:int,prices:list[int],)->int:"""Returns `countFront` for query (k, m). Returns `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=0r=min(countNoGreaterThanK,m)whilel<r:mid=(l+r)//2right=m-mid# Picking prices[mid] is better than picking prices[n - right].ifprices[mid]<2*k-prices[n-right]:l=mid+1else:r=midreturnldef_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])returnlossFront+lossBack
Thanks for stopping by! If you find this site helpful, consider buying me some protein powder to keep me fueled! π