Problem Link : The Battle of Gongmen
Author : rkr_725
Tester : mithilacoder
Editorialist : rkr_725
Difficulty : Easy
Prerequisites : Data Structure
Problem : Basically in question it is asked that a person at origin and he is having life KL. There is an array representing the coordinates of N soldiers approaching towayds the person at speed K.They can attack each other when the distance between them is less than or equal to L.There is another array representing the damaging potential of each soldier. But here is the catch that the person can select any one of the soldier in range and execute him at once,i.e., the damage by that soldier to the person will be 0. So if the person hits optimally then will he win or not?
Explanation :
Here basically we are clearly told Po can attack soldier Or a soldier can attack Po if distance between them is less than or equal to L. And it is also clear that if at a particular time if more than one soldier are in range then only Po’s life will get reduced. So Po will have to hit the soldier with maximum damage capacity such that the reduction in his life can be minimised. For this we need to maintain a priority queue in which Po will hit only the soldier at the top of priority queue and the sum of damage capacity of other soldier in priority queue will be reduced from Po’s Life.
Solution :
Setter’s Solution : UbxiDx - Online C++0x Compiler & Debugging Tool - Ideone.com
Tester’s Solution : RP9NPe - Online C++0x Compiler & Debugging Tool - Ideone.com