Picking apples off a tree
- by John Retallack
I have the following problem: I am given a tree with N apples, for each apple I am given it's weight and height. I can pick apples up to a given height H, each time I pick an apple the height of every apple is increased with U. I have to find out the maximum weight of apples I can pick.
1 = N = 100000
0 < {H, U, apples' weight and height, maximum weight} < 231
Example:
N=4 H=100 U=10
height weight
82 30
91 10
93 5
94 15
The answer is 45: first pick the apple with the weight of 15 then the one with the weight of 30.
Could someone help me approach this problem?
