PROBLEM LINK:
DSTROY - Destroy the asteroids IUPC-Plinth’20
Author - priyam2k
Editorialist - Priyam Khandelwal
DIFFICULTY:
Medium
PREREQUISITES:
Binary Search
PROBLEM:
Let an operation be to reduce exactly K elements in an array by one. Find out how many such operations are possible.
Explanation
We will use binary search on the number of minutes this operation can be done. Now how to check, if mid minutes is possible? If an element is more than mid we can reduce it mid times (add mid to sum) and if an element is less than mid (let the value of this element be x) then we can reduce this element x times (add x to sum. So when we add these numbers we will get how many operations can be done if the condition was K=1. For an arbitary K we will just have to check if \frac{sum}{mid} \geq K. If this equality holds then we can do this operation for mid minutes otherwise we can’t. The implementation is straightforward.