Разбор олимпиадной задачи — Коммерческий калькулятор

Технология и методы программирования Спортивное программирование Структуры данных Разбор олимпиадной задачи — Коммерческий калькулятор

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

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

      Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции.

      На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым, оказывается нарушен классический принцип «от перестановки мест слагаемых сумма не меняется» ).

      Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в $1.05), потом результат — с 12 ($1.65), и затем — с 13 ($2.3), то всего мы заплатим $5, если же сначала отдельно сложить 10 и 11 ($1.05), потом — 12 и 13 ($1.25) и, наконец, сложить между собой два полученных числа ($2.3), то в итоге мы заплатим лишь $4.6.

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

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

      Во входном файле INPUT.TXT записано число N (2 ≤ N ≤ 100000). Далее идет N натуральных чисел, которые нужно сложить, каждое из них не превышает 10000.

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

      В выходной файл OUTPUT.TXT выведите, сколько денег нам потребуется на нахождение суммы этих N чисел. Результат должен быть выведен с двумя знаками после десятичной точки без лидирующих нулей.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 4
      10 11 12 13
      4.60
      2 2
      1 1
      0.10

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

      Совсем неправильным подходом к решению задачи будет перебор вариантов. Нужно понять, что наиболее выгодное решение заключается в сложении минимальных чисел (жадный алгоритм). В самом деле, если мы будем складывать максимальные числа — то цена будет явно выше.

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

      Черным закрашены клетки удаленных цифр (уже сложенных), зеленым — выбранные на текущем шаге минимальные значения, синим — новые (добавляемые элементы).

      Итак, задача сводится к:

      1. последовательному выбору двух наименьших элементов;
      2. их удалению из контейнера;
      3. добавления суммы в контейнер.

      Эти шаги выполняются до тех пор, пока в контейнере не останется один элемент.

      Нужно подобрать структуру данных, обеспечивающую наивысшую эффективность этих операций. Мы рассмотрим несколько вариантов решения.

      Совсем примитивный вариант решения мог бы заключаться в хранении чисел в неупорядоченном массиве (векторе). Это значит, что поиск минимальных элементов и удаление потребуют порядка N операций. Весь алгоритм будет иметь оценку сложности O(n*n).

      Тут можно было бы вспомнить, что в стандартной библиотеке C++ есть функция partial_sort, которая выполняет частичную сортировку за O(n*m), где m — количество элементов, которые нужно упорядочить. В результате в начале массива расположатся упорядоченные m минимальных элементов. В нашей задаче таких элемента всего два (т.е. m можно принебречь) — значит мы можем получить два минимальных элемента в начале массива за O(n) операций. Этот «трюк» позволит нам выполнять удаление элемента за константное время — O(1), т.к. удаляемые элементы будут находиться в начале массива. Исходный код решения:

      #include <fstream>
      #include <vector>
      #include <iomanip>
      #include <algorithm>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        vector<long> numbers;
      
        size_t n;
        ifst >> n;
      
        numbers.resize(n);
        for (size_t i = 0; i < n; ++i) {
          ifst >> numbers[i];
        }
      
        long cost = 0;
        for (size_t i = 0; i < n-1; ++i) {
          partial_sort(numbers.begin() + i, numbers.begin() + i + 2, numbers.end());
      
          numbers[i+1] += numbers[i];
          cost += numbers[i+1];
        }
      
        ofst << setprecision(2) << std::fixed << cost*0.05;
      }

      Решение красивое, хорошо иллюстрирует суть задачи, но не достаточно быстрое — его оценка сложности все равно O(n^2).

      Очевидно, более быстрое решение должно хранить весь контейнер упорядоченным. При этом, упорядоченный вектор не подойдет, ведь вставка элемента будет занимать O(n) операций. Значит, нужны структуры, основанные на указателях.

      Перепишем это решение с использованием std::multiset — эта структура данных основана на сбалансированных деревьях поиска, за счет чего поиск, вставка и удаление элементов выполняются значительно быстрее.

      #include <fstream>
      #include <set>
      #include <iomanip>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        multiset<long> numbers;
      
        size_t n;
        ifst >> n;
      
        for (size_t i = 0; i < n; ++i) {
          long number;
          ifst >> number;
          numbers.insert(number);
        }
      
        double cost = 0;
        while (numbers.size() > 1) {
          auto first = numbers.begin(),
               second = next(first),
               third = next(second);
      
          long sum = *first + *second;
          numbers.erase(first, third);
          cost += sum;
      
          numbers.insert(sum);
        }
      
        ofst << setprecision(2) << std::fixed << cost*0.05;
      }

      Это решение проходит все тесты на acmp и работает за O(n*log(n)) операций. Для удаления элемента по значению из multimap требуется сначала найти его — O(log(n)), в то время как удаление элемента по итератору работает за O(1). В нашем решении используется интервальная версия функции удаления элементов их словаря — она принимает два итератора и удаляет элементы в диапазоне [first, last). Работает она за O(m), где m — количество удаляемых элементов, т.е. в нашем случае можно считать O(1).

      Обратите внимание, что ввод данных в multiset имеет такую же вычислительную сложность, как и остальной алгоритм, т.е. из этой структуры данных «выжать больше» уже не получится. Однако, мы на этом не остановимсяи все-таки улучшим. В самом деле, в нашем цикле самая тяжелая операция —
      это вставка элемента в multimap. В стандартной библиотеке есть оптимизированная функция вставки «with hint», принимающая дополнительно итератор, задающий примерное место вставки. Если этот итератор задает верную позицию — то вставка происходит за O(1), иначе — за O(log(n)). В нашей задаче, если сумма первых двух чисел меньше третьего — то оптимальная позиция вставки будет соответствовать итератору begin(). Теперь часть итераций цикла выполняются за O(1), а другая — за O(log(n)):

      #include <fstream>
      #include <set>
      #include <iomanip>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        multiset<long> numbers;
      
        size_t n;
        ifst >> n;
      
        for (size_t i = 0; i < n; ++i) {
          long number;
          ifst >> number;
          numbers.insert(number);
        }
      
        double cost = 0;
        while (numbers.size() > 1) {
          auto first = numbers.begin(),
               second = next(first),
               third = next(second);
      
          long sum = *first + *second;
          numbers.erase(first, third);
          cost += sum;
      
          if (sum > *third) {
            numbers.insert(sum);
          }
      
          else {
            numbers.insert(third, sum);
          }
        }
      
        ofst << setprecision(2) << std::fixed << cost*0.05;
      }

      Но и это еще не все! Наше решение можно значительно улучшить если обратить что исходные числа — целые в диапазоне [0, 10000], однако, количество чисел может доходить до 100000, но это значит, что они неизбежно будут многократно повторяться. Значит вместо дублирования чисел можно хранить их счетчик, за счет этого в контейнере будет не 100 тысяч элементов, а 10 тысяч, значит:

      1. потребление памяти сократится в 5 раз;
      2. поиск ускорится на 23%;
      3. одинаковые элементы можно обрабатывать «группами».

      Последний пункт даст наиболее значимый прирост производительности. Это значит, что для чисел 1 1 1 1 4 5 6 мы можем не добавлять двойку дважды (последовательно складывая 1+1 и 1+1), а поняв, что минимальный элемент — единица встречается 4 раза — мы добавим один раз две двойки. Если минимальный элемент встречается 100 раз — то вместо 50 операций вставки мы выполним одну. Для этого в приведенном ниже варианте решения рассчитывается количество «пар» для минимального элемента:

      #include <fstream>
      #include <map>
      #include <iomanip>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        map<long, long> numbers;
      
        size_t n;
        ifst >> n;
      
        auto insert_value = [&numbers](long number, long count) {
          auto it = numbers.find(number);
          if (it == numbers.end())
            numbers.insert(make_pair(number, count));
          else
            it->second += count;
        };
      
        for (size_t i = 0; i < n; ++i) {
          long number;
          ifst >> number;
      
          insert_value(number, 1);
        }
      
        double cost = 0;
        while (true) {
          if (numbers.size() < 2 && numbers.begin()->second < 2)
            break;
      
          auto it_first = numbers.begin();
          long first_value = it_first->first;
      
          if (it_first->second > 1) {
            long pairs_count = it_first->second / 2;
            it_first->second %= 2;
      
            insert_value(first_value*2, pairs_count);
      
            cost += first_value*pairs_count*2;
      
            if (it_first->second == 0)
              numbers.erase(it_first);
      
            continue;
          }
      
          if (numbers.size() > 1) {
            auto it_second = next(it_first);
            long second_value = it_second->first;
      
            cost += first_value + second_value;
      
            it_second->second--;
            if (it_second->second == 0)
              numbers.erase(it_first, next(it_second));
            else
              numbers.erase(it_first);
      
            insert_value(first_value+second_value, 1);
          }
        }
      
        ofst << setprecision(2) << std::fixed << cost*0.05;
      }

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