Problem Statement |
| | Badgers are lovely furry animals, and Manao has just decided to start keeping a few. The pet shop has offered him N badgers, and they are all so cute that Manao wants to take as many as he can feed. Normally, a badger needs some amount of food per day to be satisfied. However, if he sees other badgers eating, his greed awakens and he wants to eat more. A badger will want a fixed additional amount of food for each co-eater.
You're given int[]s hunger and greed, both containing N elements. The i-th element of hunger is the number of units of food that the i-th badger needs per day if he's alone. The i-th element of greed is the amount of additional units of food the i-th badger will need for each co-eater. Return the maximum number of badgers Manao can take while keeping them all satisfied if he can supply no more than totalFood units of food per day.
|
| |
Definition |
| | | Class: | Badgers | | Method: | feedMost | | Parameters: | int[], int[], int | | Returns: | int | | Method signature: | int feedMost(int[] hunger, int[] greed, int totalFood) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | hunger will contain between 1 and 50 elements, inclusive. |
| - | greed will contain the same number of elements as hunger. |
| - | Each element of hunger will be between 1 and 1000, inclusive. |
| - | Each element of greed will be between 0 and 1000, inclusive. |
| - | totalFood will be between 1 and 1000000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 2 | | Manao can take badger 0 and one of the other two badgers.
|
|
|
| 1) | |
| | | Returns: 3 | | Badger 2 is too greedy, but the rest can be fed together and will only need (5 + 2 * 0) + (2 + 2 * 2) + (5 + 2 * 1) = 18 units of food.
|
|
|
| 2) | |
| | {1,1,1,1,1} | {1000,1000,1000,1000,1000} | 10 |
| Returns: 1 | | They are too greedy to eat together.
|
|
|
| 3) | |
| | {1,2,3,4,5,6,7,8,9,10} | {10,9,8,7,6,5,4,3,2,1} | 100 |
| Returns: 5 | |
|