Football Game

Posted: 29 Sep, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Monk's favorite game is Football and his favorite club is "Manchester United". Manchester United has qualified for the Champions League Final which is to be held at the Wembley Stadium in London. So, he decided to go there and watch his favorite team play. After reaching the stadium, he saw that many people have lined up for the match tickets. He knows that there are 'M' rows in the stadium with different seating capacities. They may or may not be equal. The price of the ticket depends on the row. If the row has 'K' vacant seats, then the price of the ticket will be 'K' pounds. Now, every football fan standing in the line will get a ticket one by one.

You are given 'N' number of fans waiting for the tickets and seating capacities of different rows. The club wants to gain maximum pounds with the help of ticket sales.

Your task is to print the maximum possible pounds that the club will gain with the help of ticket sales.

Input Format:
The first line of input contains two integers 'M', and 'N', where 'M' denotes the number of rows and 'N' denotes the number of fans waiting in the line to get a ticket.

The second line contains 'M' single space-separated integers where 'VACANT_SEATS[i]' denotes the number of seats initially empty in the ith row.
Output Format:
For each output, print a single integer denoting the maximum pounds the club will earn.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= 'M' <= 5 * 10^5 
1 <= 'N' <= 10^9 
1 <= 'VACANT_SEATS[i]' <=10^9 

Time Limit: 1 sec
Approach 1

Lets first discuss the approach in steps with an example,

 

  1. The idea is to initially sort the array.
  2. Now, let the sorted array be {1, 2, 4, 6, 8} and the number of fans is 8. The team can sell a ticket of 8 pounds and again a ticket of 7 pounds as the maximum number of vacant seats remain in the last row only.
  3. The number of vacant seats thus becomes {1, 2, 4, 6, 6} and the number of fans becomes 6. Now, we can sell 2 tickets of 6 pounds and 2 of 5 pounds i.e 2 * (6 + 5) pounds can be earned.
  4. The number of vacant seats thus becomes {1, 2, 4, 4, 4} and the number of fans becomes 2. Now, we can sell 3 tickets of 4 pounds and 3 of 3 pounds i.e 3 * (4 + 3) pounds can be earned but the number of fans in the queue is 2. Thus, we can sell 2 tickets worth 4 pounds.

 

Algorithm:

 

  1. Sort the given array.
  2. Maintain a counter variable C and initialize it by 1.
  3. Maintain a variable ANS to store the answer and declare it with 0.
  4. Iterate over the array from the end.
    • If‘N is less than or equal to zero, break.
    • Initialize DIF = VACANT_SEATS[i] - VACANT_SEATS[i - 1].
    • If N >= DIF * C, we will add the sum of sequence (VACANT_SEATS[i - 1] + 1, VACANT_SEATS[i - 1] + 2,...,VACANT_SEATS[i - 1] + DIF - 1), C number of times.
    • Otherwise, initialize X = N / C, MAX= VACANT_SEATS[i - 1] + DIF
      • If X > 0, we will add the sum of sequence (MAX - X + 1, MAX - X + 2,..., MAX), C number of times. Decrease N by X * C and MAX by X.
      • Add (MAX * N) to ANS and now there is no person left, N = 0.
    • Decrease N by DIF * C, Increase C by 1.
  5. If N is still greater than zero,
    • Decrease C by 1.
    • Initialize X = N / C, MAX = VACANT_SEATS[0]
      • If X > 0, we will add the sum of sequence (MAX - X + 1, MAX - X + 2,..., MAX), C number of times. Decrease N by X * C and MAX by X.
      • Add (MAX * N) to ANS and now there is no person left, N = 0.
  6. Print ANS.
Try Problem