Given an array, you can pick exactly $$$x$$$ (where $$$x \leq 3$$$) elements in one operation and decrease each of them by 1 (all picked elements must be at least 1). You then add $$$x$$$ points to your score. You need to maximize your points with these operations applied any number of times as long as it is possible.
I think you could use a priority queue to greedily pick the top $$$x$$$ largest elements and decrease them by 1, but the problem is that the elements can go up to $$$10^{16}$$$.
Also, the length of the array is at most 200.
If you pick a element you add a point , if you pick two you add two points if you pick three elements you add 3 points.
But you decrease 1 , 2, respectively 3 vals by 3 , so if we consider the whole sum of the array you decrease the sum by 1 you increase ans by 1 so that wouldnt actually mean that the ans is the sum of the array?
No because x is given as input. We have to pick exactly x elements at once.
max_points = sum(array)
no
Is it not just the sum of the array? You just decrease all elements of the array to 0 by picking x=1.
If you MUST pick x elements, x is given in the input.
if x == 1: answer = sum(array)
if x == 2: Consider cases like [2, 5] and x = 2. The answer should be 4. find the max and set it to min(mx, rest_sum(excluding max)). answer = new_sum — new_sum % 2
if x == 3: consider cases like [1 3 5 7] and x = 3. The answer should be 12. save the max of the array and remove it from the array. Modify the array as shown in x = 2 for the new array. Then set the saved max to min(new_sum / 2, max). sum = modified_max + new_sum. answer = sum — sum % 3.
I think you can extend this for arbitrary 'x'
You mean this?
Decrement the x picked elements by the minimum of the x picked elements. Increment the ans by x*(minimum of the x picked elements).
If any of the elements after decrementing are still positive, then only push them back into the heap
If sizeof(heap) become less than x then terminate
Or
we can merge the minimum of the x picked element with the other smaller elements till it is less than equal to 2nd minimum element of the x picked elements
e.g., arr[12,11,6,4] and x=3
ans=6*3 + 4*3 i.e., 30
after above operation it will reduce the number of operations to be performed arr[12,11,10]
ans= 10*3 i.e., 30
if there are other smaller elements add them to the minimum till it is less than equal to 2nd min
Your solution doesn't work for example in 4 4 4 4 and x = 3, you pick the first three 4s. Your array becomes 0 0 0 4, and your answer 12. However we can go upto 15. Another example, 2 2 2, x = 2, your answer is 4 but it can go to 6.
Auto comment: topic has been updated by Aspergillus (previous revision, new revision, compare).