Разбор олимпиадной задачи — Азартный Шрэк

Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6228
      @admin
      StudLance.ru

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 25%):

      Как-то раз Шрек решил посетить казино. Не будучи заядлым любителем азартных игр, Шрек обнаружил, что он не знает правил ни одной из игр, доступных в казино. Недолго думая, Шрек решил все-таки поиграть. Его взор привлекла игра с довольно незамысловатыми правилами.

      На игровом столе лежат N карточек. На каждой карточке написано целое положительное число. Игра проходит между игроком и крупье. Карточки лежат на столе числами вниз. Игра заключается в том, что игрок открывает ровно N/2 карточек. Сумма всех чисел, написанных на карточках открытых игроком, называется “суммой игрока”. Следующим ходом крупье открывает оставшиеся N/2 карточек. Сумма всех чисел, написанных на карточках открытых крупье, называется “суммой крупье”. Выигрыш игрока определяется разностью чисел между “суммой игрока” и “суммой крупье”. Очевидно, что полученная разность может быть отрицательным числом. Это свидетельствует о том, что игрок проиграл и должен казино соответствующую сумму.

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

      Входные данные

      Первая строка входного файла INPUT.TXT содержит одно четное натуральное число N (2 ≤ N ≤ 100). Вторая строка входного файла содержит ровно N чисел Ai(1 ≤ Ai ≤ 10^6) – числа, написанные на игральных карточках. Все числа в строке разделяются одиночными пробелами, Ai – число, написанное на i-й карточке. Карточки нумеруются последовательно, начиная с единицы.

      Выходные данные

      Единственная строка выходного файла OUTPUT.TXT должна содержать ровно одно целое число – максимальный выигрыш, который может получить Шрек с учетом своей уникальной способности видеть числа, написанные на карточках.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 2
      1 3
      2
      2 4
      3 1 8 100
      104

      Разбор решения задачи

      Для оптимизации размера своего выигрыша, Шрек должен выбрать N/2 карт с наибольшей стоимостью. Оптимальный способ сделать это — предварительно отсортировать массив:

      #include <fstream>
      #include <vector>
      #include <numeric>
      #include <algorithm>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
        vector<int> cards;
      
        ifst >> n;
        cards.resize(n);
        for (size_t i = 0; i < n; ++i)
          ifst >> cards[i];
      
        sort(cards.begin(), cards.end(), [](int a, int b) { return a > b; });
      
        int player_sum = accumulate(cards.begin(), cards.begin()+n/2, 0);
        int banker_sum = accumulate(cards.begin()+n/2, cards.end(), 0);
      
        ofst << player_sum-banker_sum;
      }

      Тут в алгоритм сортировки передается лямбда-функция чтобы упорядочить значения по возрастанию — вместо нее можно использовать std::greater. Также, можно вообще не передавать значение в третьем аргументе — тогда будет выполнена сортировка по убыванию, значит «оптимальные» карты окажутся в конце массива. Кроме того, нам нужно выбрать лишь N/2 максимальных элементов — в сортировке остальных элементов нет необходимости — можно использовать алгоритм partial_sort.

      Для вычисления суммы первых и последних элементов используется стандартный алгоритм accumulate, вместо него можно использовать цикл (если вам так кажется понятней).

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×