2

Необходимо решить на с++ следующую задачу: можно ли отсортировать массив А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
  • 1
    Это возможно, если только в начале элементы расположены по убыванию, а следующие по возрастанию, притом если первый элемент второго отрезка больше первого элемента массива. Или же если массив полностью сортирован. Нужно только пройтись по элементам (максимум по всем) один раз 29 авг 2020 в 20:41
  • Есть же разбор и даже пример решения.
    – tym32167
    29 авг 2020 в 20:49

2 ответа 2

8

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

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

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

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

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

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

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

1

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

  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--;
        }
    }

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.