Сегодня мы будем решать Smartphone Codechef, который является частью Серии обучения DSA.
Проблема
Зональная компьютерная олимпиада 2014, 30 ноября 2013 г.
Вы разрабатываете приложение для смартфона. У вас есть список потенциальных клиентов для вашего приложения. У каждого клиента есть бюджет, и он купит приложение по объявленной вами цене тогда и только тогда, когда цена меньше или равна бюджету клиента.
Вы хотите зафиксировать цену, чтобы доход, который вы получаете от приложения, был максимальным. Найдите этот максимально возможный доход.
Например, предположим, что у вас есть 4 потенциальных клиента и их бюджеты 30, 20, 53 и 14. В этом случае максимальный доход, который вы можете получить, равен 60 .
Вход
Строка 1: N, общее количество потенциальных клиентов.
Строки со 2 по N+1: В каждой строке указан бюджет потенциального клиента.
Выход
Результат состоит из одного целого числа — максимально возможного дохода, который вы можете получить от продажи своего приложения.
Пример ввода 1
4 30 20 53 14
Пример вывода 1
60
Пример ввода 2
5 40 3 65 33 21
Пример вывода 2
99
Объяснение
Тестовые данные
Бюджет каждого клиента составляет от 1 до 108 включительно.
Подзадача 1 (30 баллов): 1 ≤ N ≤ 5000.
Подзадача 2 (70 баллов): 1 ≤ N ≤ 5×105.
Данные оценки в реальном времени
Во время экзамена на сервере имеется 15 тестовых входов. Группировка по подзадачам выглядит следующим образом.
• Подзадача 1: проверка входных данных 0,…,5.
• Подзадача 2: проверка входных данных 6,…,14.
Примечание
Ответ может не поместиться в переменной типа int. Мы рекомендуем использовать переменные типа long long для чтения ввода и вычисления ответа. Если вы используете printf и scanf, вы можете использовать %lld для long long.
