Разбор олимпиадной задачи — Волосатый бизнес

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

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

      Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на жизнь. Поразмыслив, он решил, что сможет иметь очень неплохие деньги на продаже собственных волос. Известно, что пункты приема покупают волосы произвольной длины стоимостью С у.е. за каждый сантиметр. Так как волосяной рынок является очень динамичным, то цена одного сантиметра волос меняется каждый день как и курс валют. Неформал является очень хорошим бизнес-аналитиком. Он смог вычислить, какой будет цена одного сантиметра волос в каждый из ближайших N дней (для удобства пронумеруем дни в хронологическом порядке от 0 до N-1). Теперь он хочет определить, в какие из этих дней ему следует продавать волосы, чтобы по истечению всех N дней заработать максимальное количество денег. Заметим, что волосы у неформала растут только ночью и вырастают на 1 сантиметр за ночь. Следует также учесть, что до 0-го дня неформал с горя подстригся наголо и к 0-му дню длина его волос составляла 1 сантиметр.

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

      В первой строке входного файла INPUT.TXT записано целое число N (0 < N ≤ 100). Во второй строке через пробел заданы N натуральных чисел, не превосходящих 100, соответствующие стоимости C[i] 1 сантиметра волос за каждый i-й день.

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

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

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 5
      73 31 96 24 46
      380
      2 10
      1 2 3 4 5 6 7 8 9 10
      100
      3 10
      10 9 8 7 6 5 4 3 2 1
      55

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

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

      #include <fstream>
      #include <vector>
      
      using namespace std;
      
      size_t max_cash(vector<size_t>& costs, size_t day, size_t length, size_t cash) {
        if (day >= costs.size())
          return cash;
      
        auto sale_case = max_cash(costs, day+1, 1, cash+costs[day]*length);
        auto save_case = max_cash(costs, day+1, length+1, cash);
      
        return max(sale_case, save_case);
      }
      
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
      
        ifst >> n;
        vector<size_t> costs(n);
      
        for (size_t i = 0; i < n; ++i) {
          ifst >> costs[i];
        }
      
        ofst << max_cash(costs, 0, 1, 0) << endl;
      }

      В функции max_cash мы получаем оценки каждого случая — нам нужно вернуть максимальную из них. В результате работы этой функции будет построено что-то типа дерева, где из каждого узла выходит две дуги (продали/нет). Выглядит это примерно так:

      Количество узлов в дереве можно оценить как 2^N — это количество вызовов функций. Для большого значения N такое решение не годится, нужно что-то оптимизировать.

      В самом деле, стоит ли продавать волосы на i-том дне если завтра они стоят дороже? — очевидно нет. Вы можете записать такое нехитрое правило и заметить как вырастет производительность, однако и этого не достаточно. Стоит ли продавать сегодня, если завтра дешевле, а послезавтра — дороже? — очевидно тоже нет.

      Продолжая такие рассуждения можно прийти к тому, что первая продажа должна произойти в день когда цена максимальная (пусть это будет день d). Мы поняли, что до дня d ничего продавать не нужно, к этому дню мы накопим d сантиметров волос. Дальше — аналогичным образом рассмотрим часть массива, расположенную правее d. С следующем примере для решения потребуется 5 шагов (именно столько раз мы выполним поиск максимума в части массива) — сравните с предыдущим подходом, который потребовал бы 1024 рекурсивных вызова:

      Соответствующий исходный код:

      #include <fstream>
      #include <vector>
      #include <algorithm>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n, cash = 0;
      
        ifst >> n;
        vector<size_t> costs(n);
      
        for (size_t i = 0; i < n; ++i) {
          ifst >> costs[i];
        }
      
        auto current_day = costs.begin();
      
        while (current_day != costs.end()) {
          auto next_sale_day = max_element(current_day, costs.end());
      
          cash += *next_sale_day * (distance(current_day, next_sale_day)+1);
      
          current_day = next(next_sale_day);
        }
      
        ofst << cash << endl;
      }

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

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

      #include <fstream>
      #include <vector>
      #include <set>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
      
        ifst >> n;
        vector<size_t> costs(n);
        multiset<size_t, greater<size_t>> sorted_costs;
      
        for (size_t i = 0; i < n; ++i) {
          ifst >> costs[i];
          sorted_costs.insert(costs[i]);
        }
      
        size_t length = 1;
        size_t cash = 0;
        for (size_t i = 0; i < n; ++i) {
          if (costs[i] == *sorted_costs.begin()) {
            cash += costs[i] * length;
            length = 0;
          }
      
          sorted_costs.erase(sorted_costs.find(costs[i]));
          ++length;
        }
        ofst << cash << endl;
      }
      

      В этом, новом решении помимо курсов волос к рублю, такие же данные хранятся (дублируются) упорядоченными. Для этого используется multiset, внутри которого реализовано дерево поиска, а данные в нем могут дублироваться.

      При вводе стоимости волос за i-тый день теперь происходит вставка в multiset — поэтому весь ввод теперь занимает O(N*log(N)) операций. Дни теперь обрабатываются не «пачками», а последовательно. Если стоимость волос за текущий день совпадает со стоиомостью в первом элементе multiset — значит текущий день является максимумом в своей части массива и нужно выполнить продажу. В любом случае после обработки текущего дня его нужно выкинуть из multiset. Хорошо разберитесь с тем как это работает — это тоже очень полезное упражнение.

      На схеме показаны первые шаги алгоритма. Видно, что продажа происходит только если первый элемент упорядоченной копии массива совпадает с текущим обрабатываемым. Для хранения упорядоченного массива мы использовали multimap именно потому, что помимо сортировки нам нужно быстро находить и удалять элементы — т.е. массив не подойдет.

      Однако, прекрасно подойдет словарь, за счет его использования мы можем сэкономить память — ведь вместо хранения одинаковых курсов можно хранить счетчик:

      #include <fstream>
      #include <vector>
      #include <map>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t n;
      
        ifst >> n;
        vector<size_t> costs(n);
        map<size_t, size_t, greater<size_t>> sorted_costs;
      
        for (size_t i = 0; i < n; ++i) {
          ifst >> costs[i];
          ++sorted_costs[costs[i]];
        }
      
        size_t length = 1;
        size_t cash = 0;
        for (size_t i = 0; i < n; ++i) {
          if (costs[i] == sorted_costs.begin()->first) {
            cash += costs[i] * length;
            length = 0;
          }
      
          --sorted_costs[costs[i]];
          if (sorted_costs[costs[i]] == 0)
            sorted_costs.erase(costs[i]);
      
          ++length;
        }
        ofst << cash << endl;
      }

      StudLance.ru

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