AnswerBun.com

Оптимизация медленного алгоритма

Необходимо решить на с++ следующую задачу: можно ли отсортировать массив Аrr (по возрастанию), выполнив переворот ровно одного подотрезка (части массива) Аrr? Если да, вывести "yes" и индексы начала подотрезка.
В противном случае вывести "no". Подробнее https://codeforces.com/problemset/problem/451/B.

Мною был создан следующий алгоритм: Во вложенном цикле создаётся частично перевернутый по индексам переворота i и j(которые и перебираются во вложенном цикле) массив. При совпадении полученного таким способом массива Q и заранее отсортированного массива В выводятся индексы i и j. Ниже приведена функция переворота части массива.

Далный алгоритм работает правильно, но на одном из тестов (70+к размер массива) тестировщик выводит превышение лимита времени. Как значительно оптимизировать перебор индексов или функцию переворота части массива для уменьшения времени работы программы?
Функция переворота части массива:

vector<int> reverse(int l, int r, vector<int> A){
for(int i = l;i<=(l+r)/2;i++)
{
    swap(A[i],A[l-i+r]);
}
return A;
}

Если существенная оптимизация невозможна прошу привести более быстрый способ решения задачи.

2 Answers

Возможна следющая оптимизация.

Для того, чтобы вывести ответ, не нужно переворачивать массив.

Нужно просто пройтись по нему, и посчитать, сколько раз происходит смена "убывания-возрастания" значений. Это делается сравнением соседних элементов массива.

Тогда если такое изменение происходит 0, 1 или 2 раза - то "да", есть монотонный кусок массива, перевернув который Вы МОЖЕТЕ получить монотонно отсортированный массив. Если таких смен возрастания-убывания больше - уже не сможете.

Но при этом надо проверить дополнительное условие: что внутри мнотонного подотрезка все значения не меньше значений в одной строне от него и не больше значений в другой стороне.

Я надеюсь, что объяснил достаточно понятно.

Если не поможет - напишите в комментариях, я напишу код

Correct answer by S.H. on December 28, 2020

Алгоритм простой.

  1. Найти начало перевернутого участка
  2. Найти конец перевернутого участка
  3. Перевернуть
  4. Проверить стал ли массив сортированным

Код будет примерно такой (C#)

    private static void Solve(int[] numbers)
    {
        int start = 0;
        int end = numbers.Length - 1;

        while (start < numbers.Length - 1 && numbers[start] < numbers[start + 1])
            start++;
        while (start > 0 && numbers[start] < numbers[start - 1])
            start--;

        while (end > 0 && numbers[end] > numbers[end - 1])
            end--;
        while (end < numbers.Length - 1 && numbers[end] > numbers[end + 1])
            end++;

        if (end < start) end = start;

        swap(numbers, start, end);

        for (int i = 0; i < numbers.Length - 1; i++)
        {
            if (numbers[i] > numbers[i + 1])
            {
                Console.WriteLine("no");
                return;
            }
        }

        Console.WriteLine("yes");
        Console.WriteLine("{0} {1}", start + 1, end + 1);
    }

Функция переворачивания

    private static void swap(int[] arr, int start, int end)
    {
        while (start < end)
        {
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
    }

Заодно отправил решение.

Answered by tym32167 on December 28, 2020

Add your own answers!

Related Questions

Cервисы для удаленной разработке на macOS

0  Asked on December 10, 2020 by oleg-stepanov

   

Группировка RecyclerView Android

1  Asked on December 10, 2020 by grand

       

Cookie и private api instagram

1  Asked on December 10, 2020 by brainswitch

     

Отправить ajax и получить ответ

1  Asked on December 7, 2020 by js-student

       

Закрасить половину окна java swing

1  Asked on December 7, 2020 by playrus

   

Подмена цвета PNG при наведении мыши

3  Asked on December 6, 2020 by vadim-rudenko

       

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved.