На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Найти сумму целых чисел с условием минимальной стоимости
    Всем хай! Сходу к делу!

    Есть такая задачка. Дано N (натуральное число, не превышающее 300 000) - количество натуральных чисел в последовательности. Есть только одна операция: взять 2 любых числа и сложить их. Стоимость этой операции равна их сумме. Надо просуммировать все числа (получить скаляр), чтобы стоимость всех операций сложения была минимальной.

    Пример:
    N = 5
    7 2 11 3 6
    1. 2 + 3 = 5 (стоимость = 5) ---> 7 5 11 6
    2. 5 + 6 = 11 (cost = 5 + 11 = 16) ---> 7 11 11
    3. 7 + 11 = 18 (cost = 16 + 18 = 34) ---> 11 18
    4. 11 + 18 = 29 (cost = 34 + 29 = 63) ---> 29 ---> end

    Ответ: 63
    -------------------------
    я правильно понимаю, что здесь достаточно брать 2 наименьших числа из текущей последовательности и суммировать их? вроде, да.

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

    Еще есть вариант - завести доп.массив текущих стоимостей. Просуммировали 2 числа - сумму отправили в этот массив. Очевидно, что тек. стоимость (не общая) на каждом след.шаге возрастает. Затем надо брать не 2 мин.числа из исходного массива, а смотреть на возможные сочетания элементов из исходно массива и массива стоимостей. Но там как-то помечать еще надо, что тек.стоимость использовали и пр. пр. Как-то мутно все это...


    что здесь самое оптимальное по алгоритму?

    спс за внимание

    p.s. это задача с упором на оптимизацию, требуется сверхскоростное решение + мин.объем используемой памяти)
      Если действовать "влоб", то в конечной сумме два числа, использованные в первом суммировании, входят в итог 4 раза, во втором - три, в третьем - два, в последнем - 1.

      Т.е. задача сводится к минимизации функции 4*a(1)+4*a(2)+3*a(3)+2*a(4)+a(5) на заданном наборе чисел (найти минимизирующую перестановку).

      1) Берём любую перестановку. Считаем её текущим минимумом.

      2) Берём любую перестановку, отличающуюся одной парой (два числа поменены местами). Зная их индексы, легко посчитать изменение итога. Перебираем все перестановки, если ни одна не привела к уменьшению итога - получен ответ, выводим и завершаем.

      3) Если же на очередном обмене получено уменьшение итога - фиксируем новое состояние текущего минимума и повторяем пункт 2.

      Что у функции нет локальных минимумов, доказывать не готов.

      Цитата FasterHarder @
      достаточно брать 2 наименьших числа из текущей последовательности и суммировать их

      Это "жадный" алгоритм в данном случае. Впрочем, трудно придумать, почему он может дать НЕ оптимум.
        Цитата Akina @
        Т.е. задача сводится к минимизации функции 4*a(1)+4*a(2)+3*a(3)+2*a(4)+a(5) на заданном наборе чисел (найти минимизирующую перестановку).

        это интересный подход

        Цитата Akina @
        Перебираем все перестановки

        ВСЕ перестановки?) Длина входной последовательности (макс.случай) = 300 000, вроде по формулам из комбинаторики всего 300 000! перестановок будет)
        т е это метод ГРУБОЙ СИЛЫ получается? А он точно оптимален по скорости?) Хотя я здесь, скорее всего, не до конца еще понимаю, о каких перестановках говоришь, т к всего предлагаешь менять по 2 элемента, т е их будет гораздо меньше, чем "факториал".

        Но с др.стороны, ведь есть отличная штука, вот эта:
        Цитата Akina @
        4*a(1)+4*a(2)+3*a(3)+2*a(4)+a(5)

        как я понял, а(1) - самый мин, а(2) - 2ой по мин. и пр.
        Достаточно ТОЛЬКО отсортировать и подставить в эту "функцию" и ответ ГОТОВ. Разве это не лучший способ решения? Единственная трата времени - на сортировку. Ну, можно взять Хоара (qsort) и все. + я вроде хорошо понял этот способ решения (в отличие от перестановок)
          Представь, что у тебя есть некое промежуточное ..+12345*a(54321)+12344*a(54322)+..
          Обменяем их местами: ..+12345*a(54322)+12346*a(54321)+..
          Изменение суммы будет a(54322)-a(54321).
          Если изначально числа были расположены по возрастанию, то изменение положительно, т.е. такой обмен - затея неудачная.
          То же для обмена двух не-соседних.

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

            ExpandedWrap disabled
              #include <iostream>
              #include <algorithm>
              #include <vector>
               
              using namespace std;
               
              void main(void)
              {
                  int n;
                  cin >> n;
               
                  vector<int> numbers(n);
                  for(int i = 0; i < n; i++)
                      cin >> numbers[i];
                  std::sort(numbers.begin(), numbers.end());
                  
                  // считаем целевую мин.функцию
                  double cost_total = (n - 1) * numbers[0];
                  for(int i = 1; i < n; i++)
                      cost_total += (n - i) * numbers[i];
               
                  cout << cost_total;
                  cin.get();
              }


            все шикарно работает)
            у меня лимит по времени 1.5 сек. на выполнение, здесь же, при самой длинной вх.последовательности (300К чисел) работает быстрее секунды (проверил через случ.заполнение rand()).

            Akina, поклон за эту минимизирующую функцию)

            Добавлено
            нашелся тест, на котором программа выдается неправильный результат:
            ExpandedWrap disabled
              n = 10
              {18, 42, 63, 26, 15, 19, 11, 29, 26, 24}


            программа выдает 1123, а должно быть 869...причем я не поленился и перепроверил в excel, да, верный ответ 869 (не опечатка)

            ведать есть какая-то тонкость в этой целевой функции, либо ошибка в коде (хотя код вроде из разряда простых + на остальных тестах были совпадающие ответы)...
              NP-полная задача о рюкзаке. Найдёте быстрое решение - сделаете революцию.
                кажется вкурил, что вот, например на таком ряде: {1, 1, 1, 1, 1, 2, 2, 2, 3}
                1 итерация: 1 + 1 = 2 ---> {1, 1, 1, 2, 2, 2, 2, 3} и эта "синяя" минимальная единица ПРОПУСКАЕТ следующие итерации нахождения стоимости...

                в итоге, наверное, возможен случай, когда в целевой функции вообще не будет ни одного числа, которое встречается в суммах стоимостей (n-1) раз, следовательно, мое предположение, что в функции а(1) - 1ое мин, а(2) - 2ое мин является ошибочным.

                А если делать полный перебор здесь, то явно за 1.5 сек. не уложится)

                зы: как всегда все тоньше, нааааааамного тоньше...

                Добавлено
                короче, вот правильно считающая программа, правда она умирает по скорости уже от 10К элементов ))
                для последовательности 300К чисел, думаю, что она "никогда" не посчитает)

                ExpandedWrap disabled
                  #include <iostream>
                  #include <algorithm>
                  #include <vector>
                   
                  using namespace std;
                   
                  void main(void)
                  {
                      int n;
                      cin >> n;
                   
                      vector<int> numbers(n);
                      for(int i = 0; i < n; i++)
                          cin >> numbers[i];
                      std::sort(numbers.begin(), numbers.end());
                   
                      double cost_total = 0;
                   
                      while(numbers.size() != 1)
                      {
                          double current_sum = numbers[0] + numbers[1];
                          cost_total += current_sum;
                          numbers.erase(numbers.begin(), numbers.begin() + 2);
                          auto it = std::lower_bound(numbers.begin(), numbers.end(), current_sum);
                          numbers.insert(it, current_sum);
                      }  
                   
                      cout << cost_total;
                      cin.get();
                  }
                  FasterHarder
                  Бросайте уже спортивное программирование. Самостоятельно это не освоить. Есть специальные курсы, где на это натаскивают. У каждого спортсмена есть тренер - бывший или действующий программист-олимпиадник. Вам оно надо?
                  От спортивного программирования до промышленного как пешком до Луны.
                    Ну вот зачем в такой простой задаче использовать все эти навороченные вектора, итераторы, курсоры (или что там используется - я не силен в эльфийском). Достаточно обычного массива. Читаем количество элементов N, выделяем массив a[N], заполняем массив, сортируем по возрастанию. Затем в цикле i = 1..(N-1):

                    a[i] += a[i-1]
                    sum += a[i]
                    j := i
                    пока a[j] > a[j+1] && j < (N-1): a[j] <-> a[j+1], j++
                      вариант из поста №9 был частично рассмотрен выше, но мне казалось, что сдвиги будут долго выполняться, т к могут продолжаться на много элементов, но, написав эту программу, все отлично по скорости, и 300К за 1.5 сек.вполне рассчитывается.

                      Поэтому, да, этот алгоритм здесь оказался подходящим, признаю AVA12, ну, спс

                      вот программка:
                      ExpandedWrap disabled
                        #include <iostream>
                        #include <algorithm>
                        #include <vector>
                         
                        using namespace std;
                         
                        void main(void)
                        {
                            int n;
                            cin >> n;
                         
                            vector<int> numbers(n);
                            for(int i = 0; i < n; i++)
                                cin >> numbers[i];
                                //numbers[i] = rand() % 101 - 50;
                            std::sort(numbers.begin(), numbers.end());
                         
                            double cost_total = 0;
                         
                            for(int i = 1; i < n; i++)
                            {
                                numbers[i] += numbers[i - 1];
                                cost_total += numbers[i];
                         
                                int j = i;
                                while((j < (n - 1)) && (numbers[j] > numbers[j + 1]))
                                {
                                    std::swap(numbers[j], numbers[j + 1]);
                                    j++;
                                }
                            }  
                         
                            cout << cost_total;
                            cin.get();
                        }
                        Цитата FasterHarder @
                        ExpandedWrap disabled
                          #include <iostream>
                          #include <algorithm>
                          #include <vector>

                        В олимпиадном программировании любые библиотеки за исключением ввода-вывода запрещены.
                        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                        0 пользователей:


                        Рейтинг@Mail.ru
                        [ Script execution time: 0,0333 ]   [ 15 queries used ]   [ Generated: 19.03.24, 08:44 GMT ]