TopCoder problem "TaliluluCoffee" used in TCHS08 Round 1 (Division I Level Two)



Problem Statement

    

A new coffee place opened on the campus of Talilulu University. Things work differently at this coffee place. Every customer arrives at time 0, and the owner decides the order in which to serve them. A single customer is served each second, until all the customers have been served. The first customer is served at second 0. If customer i is served at time t seconds, he will pay tips[i] - t. If this number is negative, he will not pay a tip at all. Given a int[] tips return the maximum amount of money the owner can make in tips.

 

Definition

    
Class:TaliluluCoffee
Method:maxTip
Parameters:int[]
Returns:int
Method signature:int maxTip(int[] tips)
(be sure your method is public)
    
 

Constraints

-tips will contain between 0 and 50 elements, inclusive.
-Each element of tips will be between 0 and 100000, inclusive.
 

Examples

0)
    
{3, 3, 3, 3}
Returns: 6
The order in which the customers will be served is not relevant because all tips are the same.
1)
    
{3, 2, 3}
Returns: 5
A good solution is: first serve the second customer, then serve the third one, then the first one. The profit from tips will be 2 + (3 - 1) + (3 - 2) = 2 + 2 + 1 = 5.
2)
    
{7, 8, 6, 9, 10}
Returns: 30
3)
    
{1, 1, 1, 1, 2}
Returns: 2
4)
    
{1, 2, 3}
Returns: 4

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8197

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11153&pm=8197

Writer:

vlad_D

Testers:

PabloGilberto , Olexiy , ivan_metelsky , andrewzta

Problem categories:

Greedy