Рубрики

Найти максимальную сумму, которую можно собрать, продавая билеты в кино

Учитывая целое число N и массив мест [], где N — это количество людей, стоящих в очереди, чтобы купить билет в кино, а seat [i] — количество свободных мест в i- м ряду кинотеатра. Задача состоит в том, чтобы найти максимальную сумму, которую может получить владелец кинотеатра, продавая билеты в кино N людям. Цена билета равна максимальному количеству свободных мест среди всех рядов.

Пример:

Input: seats[] = {1, 2, 4}, N = 3
Output: 9

4 + 3 + 2 = 9

Input: seats[] = {2, 3, 5, 3}, N = 4
Output: 15

Подход. Эту проблему можно решить с помощью очереди с приоритетами, в которой будет храниться количество свободных мест для каждого ряда, а максимальное количество из них будет доступно вверху.

  • Создайте пустой файл priority_queue q, пройдитесь по массиву seat [] и вставьте все элементы в файл priority_queue.
  • Инициализируйте две целочисленные переменные ticketSold = 0 и ans = 0, которые будут хранить количество проданных билетов и общую сумму на данный момент.
  • Теперь проверьте, когда ticketSold <N и q.top ()> 0, затем удалите верхний элемент из priority_queue и обновите ans, добавив верхний элемент очереди с приоритетами. Также сохраните это верхнее значение в переменной temp и вставьте temp — 1 обратно в priority_queue.
  • Повторяйте эти шаги, пока все люди не будут проданы билеты и распечатайте окончательный результат.

Ниже приведена реализация вышеуказанного подхода:

C ++

PersonEmpty SeatsTicket Cost
11 2 44
21 2 33
31 2 22

Джава

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата максимальной суммы
// что можно получить, продав билеты

int maxAmount(int M, int N, int seats[])

{

  

    // Приоритетная очередь, в которой хранятся

    // количество свободных мест

    priority_queue<int> q;

  

    // Вставляем каждый элемент массива

    // в очередь приоритетов

    for (int i = 0; i < M; i++) {

        q.push(seats[i]);

    }

  

    // Для сохранения итогов

    // количество проданных билетов

    int ticketSold = 0;

  

    // Для сохранения общей суммы

    // коллекции

    int ans = 0;

  

    // Пока продано билетов меньше чем N

    // и q.top> 0 затем обновляем собранный

    // сумма с вершиной приоритета

    // очередь

    while (ticketSold < N && q.top() > 0) {

        ans = ans + q.top();

        int temp = q.top();

        q.pop();

        q.push(temp - 1);

        ticketSold++;

    }

  

    return ans;

}

  
// Код драйвера

int main()

{

    int seats[] = { 1, 2, 4 };

    int M = sizeof(seats) / sizeof(int);

    int N = 3;

  

    cout << maxAmount(N, M, seats);

  

    return 0;

}

Выход:

9

Рекомендуемые посты:

Найти максимальную сумму, которую можно собрать, продавая билеты в кино

0.00 (0%) 0 votes