Problem Statement:
There is an array "cost" of length n, cost[i] is the cost of i'th robot and an array "A" of length n, A[i] is the number written on the i'th robot, you are also given an integer K which is the amount you have. You can buy a robot only if cost of that robot is less than or equal to the remaining amount you have(obviously).
Suppose you buy x robots with indices i1, i2, i3 ... ix then you will get one gift card for each i such that A[i] >= x (i belongs to indices of robots you purchased). Calculate the maximum number of gift cards you can get.
Constraints
1<= n <= 100
1<= K <= 1e9
1<= cost[i] <= 1e4
1<= A[i] <= n
Sample Input
5 300 <-- (n, K)
4 5 4 3 2 <-- (cost)
120 150 80 90 100 <-- (A)
Sample Output
2
Explanation
Buy robots with indices 3,4,5 cost 270(<=300) and you will get 2 gift cards for robots 4 and 5
I was thinking of some knapsack type approach but was not able to get a solution. You can comment your solution or post a link to a similar problem with solution, thanks.
Till I am able to think you can do it with binary search
Ist observation : if you buy k robots and gift you get let y (y < k) then it is optimal to just buy y robots so that you get also y gift
Ex -> let you buy i1 i2 i3 i4 i5 , corresponding A[i] value 6 5 1 2 2 it is optimal to buy 6 5 only since these are contributing
Now Our goal to maximize the y(robot you buy and all contributing to the answer)
Binary Search over y (1...n) for fix y you can club the elements that has A[i] >= y then you pick smallest y elements among them and check their sum <= k or not
I think this works fine , If not plz let me know