Distribution Apples
We were given N apple trees and M friends. The ith tree has a[i] apples and it takes b[i] units of energy to pluck an apple from this tree. Find the maximum number of apples while minimizing the energy required to pluck them such that they distribute apples among themselves equally.
Examples:
Input: N = 4, M = 5, a[] = {5,5,1,1} , b[] = {1,2,5,5}
Output: {10, 15}
Explanation: 5 apples from 1st tree, 5 apples from 2nd tree, and none from 3rd and 4th tree. This way, they are able to pluck 10 apples and the energy spent is 15.Input: N = 3, M = 3 , a[] = {3, 3, 3}, b[] = {3, 5, 1}
Output: {9, 27}
Explanation: All apples can be plucked as friends can distribute them equally.
Approach: This can be solved with the following idea:
By checking the number of apples that can be distributed among m friends (Number of apples % m). Using Priority queue, we can easily find out minimum energy to get the apples. As it always optimal to get the apples using minimum energy given in B. Then find the energy required for all friends.
Below are the steps involved:
- Initialize a priority_queue, the top element stores the minimum element.
- Count the total number of apples.
- Check the number of apples that can be given to each friend.
- Now, to minimize energy:
- Iterate over priority_queue to check how many apples are there for that energy.
- According to that, we can decrease the total.
- Return {total, energy}.
Below is the implementation of the code:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to calculate maximum apples and minimum // energy vector< long long > calc( int n, int m, vector< int > a, vector< int > b) { // Function to store ans vector< long long > ans; // Priority queue instialising priority_queue<pair< long long , long long >, vector<pair< long long , long long > >, greater<pair< long long , long long > > > pq; // Iterate over energy array for ( int i = 0; i < n; i++) { pq.push(make_pair(b[i], i)); } // Calculate total apples long long total = 0; for ( int i = 0; i < n; i++) { total += a[i]; } // Count apples per friend total -= total % m; long long energy = 0; ans.push_back(total); // Count minimum energy possible while (total > 0) { // If total apples are more if (a[pq.top().second] <= total) { energy += (pq.top().first) * (a[pq.top().second]); total -= a[pq.top().second]; pq.pop(); } // If apple count is less else if (a[pq.top().second] > total) { energy += (pq.top().first) * (total); total = 0; } } // Add energy to ans ans.push_back(energy); return ans; } // Driver code int main() { int n = 4; int m = 4; vector< int > a = { 1, 1, 2, 1 }; vector< int > b = { 2, 3, 4, 4 }; // Function call vector< long long > ans = calc(n, m, a, b); for ( auto a : ans) { cout << a << " " ; } return 0; } |
Java
import java.util.*; public class Solution { // Function to calculate maximum apples and minimum // energy public static List<Long> calc( int n, int m, List<Integer> a, List<Integer> b) { // Function to store ans List<Long> ans = new ArrayList<>(); // Priority queue initialization PriorityQueue<Pair<Long, Long>> pq = new PriorityQueue<>(Comparator.comparingLong(Pair::getFirst)); // Iterate over energy array for ( int i = 0 ; i < n; i++) { pq.offer( new Pair<>(( long ) b.get(i), ( long ) i)); } // Calculate total apples long total = 0 ; for ( int i = 0 ; i < n; i++) { total += a.get(i); } // Count apples per friend total -= total % m; long energy = 0 ; ans.add(total); // Count minimum energy possible while (total > 0 ) { // If total apples are more if (a.get(( int ) ( long ) pq.peek().getSecond()) <= total) { energy += pq.peek().getFirst() * a.get(( int ) ( long ) pq.peek().getSecond()); total -= a.get(( int ) ( long ) pq.peek().getSecond()); pq.poll(); } // If apple count is less else if (a.get(( int ) ( long ) pq.peek().getSecond()) > total) { energy += pq.peek().getFirst() * total; total = 0 ; } } // Add energy to ans ans.add(energy); return ans; } // Driver code public static void main(String[] args) { int n = 4 ; int m = 4 ; List<Integer> a = Arrays.asList( 1 , 1 , 2 , 1 ); List<Integer> b = Arrays.asList( 2 , 3 , 4 , 4 ); // Function call List<Long> ans = calc(n, m, a, b); for ( long val : ans) { System.out.print(val + " " ); } } // Custom Pair class since Java doesn't have a built-in Pair class static class Pair<K, V> { private final K first; private final V second; Pair(K first, V second) { this .first = first; this .second = second; } public K getFirst() { return first; } public V getSecond() { return second; } } } // This code is contributed by akshitaguprzj3 |
Python3
# Python Implementation import heapq # Function to calculate maximum apples and minimum energy def calc(n, m, a, b): # List to store results ans = [] # Priority queue initialization pq = [] # Iterate over energy array for i in range (n): heapq.heappush(pq, (b[i], i)) # Calculate total apples total = sum (a) # Count apples per friend total - = total % m energy = 0 ans.append(total) # Count minimum energy possible while total > 0 : # If total apples are more if a[pq[ 0 ][ 1 ]] < = total: energy + = pq[ 0 ][ 0 ] * a[pq[ 0 ][ 1 ]] total - = a[pq[ 0 ][ 1 ]] heapq.heappop(pq) # If apple count is less elif a[pq[ 0 ][ 1 ]] > total: energy + = pq[ 0 ][ 0 ] * total total = 0 # Add energy to ans ans.append(energy) return ans # Driver code if __name__ = = "__main__" : n = 4 m = 4 a = [ 1 , 1 , 2 , 1 ] b = [ 2 , 3 , 4 , 4 ] # Function call ans = calc(n, m, a, b) for a in ans: print (a, end = " " ) # This code is contributed by Sakshi |
C#
using System; using System.Collections.Generic; class Program { // Function to calculate maximum apples and minimum energy static List< long > Calc( int n, int m, List< int > a, List< int > b) { // Function to store ans List< long > ans = new List< long >(); // Priority queue initializing SortedSet<( long , long )> pq = new SortedSet<( long , long )>(); // Iterate over energy array for ( int i = 0; i < n; i++) { pq.Add((b[i], i)); } // Calculate total apples long total = 0; foreach ( int apples in a) { total += apples; } // Count apples per friend total -= total % m; long energy = 0; ans.Add(total); // Count minimum energy possible while (total > 0) { // If total apples are more if (a[( int )pq.Min.Item2] <= total) { energy += pq.Min.Item1 * a[( int )pq.Min.Item2]; total -= a[( int )pq.Min.Item2]; pq.Remove(pq.Min); } // If apple count is less else if (a[( int )pq.Min.Item2] > total) { energy += pq.Min.Item1 * total; total = 0; } } // Add energy to ans ans.Add(energy); return ans; } // Driver code static void Main() { int n = 4; int m = 4; List< int > a = new List< int > { 1, 1, 2, 1 }; List< int > b = new List< int > { 2, 3, 4, 4 }; // Function call List< long > ans = Calc(n, m, a, b); foreach ( long value in ans) { Console.Write(value + " " ); } } } |
Javascript
function calc(n, m, a, b) { // Store the answer let ans = []; // Priority queue (min-heap) initialization let pq = new PriorityQueue((a, b) => a[0] < b[0]); // Populate the priority queue for (let i = 0; i < n; i++) { pq.enqueue([b[i], a[i]]); } // Calculate total apples let total = a.reduce((acc, val) => acc + val, 0); total -= total % m; let energy = 0; ans.push(total); // Calculate minimum energy while (total > 0) { let [curEnergy, curApples] = pq.dequeue(); if (curApples <= total) { energy += curEnergy * curApples; total -= curApples; } else { energy += curEnergy * total; total = 0; } } ans.push(energy); return ans; } // Simple priority queue implementation for demonstration class PriorityQueue { constructor(comparator) { this .values = []; this .comparator = comparator || ((a, b) => a > b); } enqueue(val) { this .values.push(val); this .values.sort((a, b) => this .comparator(a, b) ? 1 : -1); } dequeue() { return this .values.shift(); } } // Driver code function main() { const n = 4; const m = 4; const a = [1, 1, 2, 1]; const b = [2, 3, 4, 4]; const ans = calc(n, m, a, b); console.log(ans.join( ' ' )); } main(); // This code is contributed by akshitaguprzj3 |
4 13
Complexity Analysis:
Time Complexity: O(N log N)
Auxiliary Space: O(N)
Contact Us