Рубрики

Проверьте, можно ли расположить элементы массива в круг с последовательной разницей в 1

Учитывая массив номера. Задача состоит в том, чтобы проверить, можно ли расположить все числа по кругу так, чтобы любые два соседних числа различались ровно на 1. Выведите «ДА», если возможно получить такое расположение, и «НЕТ» в противном случае.

Примеры:

Input: arr[] = {1, 2, 3, 2}
Output: YES
The circle formed is:
         1
     2       2
         3   

Input: arr[] = {3, 5, 8, 4, 7, 6, 4, 7}
Output: NO

Ниже приведен пошаговый алгоритм решения этой проблемы:

  1. Сначала вставьте все элементы в мультимножество.
  2. Удалите первый элемент набора и сохраните его в переменной curr .
  3. Пройдите до тех пор, пока размер мультимножества не уменьшится до 0.
    • Удалите элементы, которые на 1 больше или на 1 меньше значения curr .
    • Если есть значение с разницей больше 1, то «круг невозможен».
  4. Убедитесь, что начальные и конечные значения curr varaible одинаковы, выведите «YES», если это так, в противном случае выведите «NO».

Ниже приведена реализация вышеуказанного подхода:

// C ++ программа для проверки наличия элементов массива
// можно расположить в круг с последовательным
// разница как 1

  
#include <bits/stdc++.h>

using namespace std;

  
// Функция для проверки, могут ли элементы массива
// располагаться по кругу с последовательным
// разница как 1

int circlePossible(int arr[], int n)

{

    multiset<int> s;

  

    // Инициализируем мультимножество с массивом

    // элементы

    for (int i = 0; i < n; i++)

        s.insert(arr[i]);

  

    // Получить указатель на первый элемент

    int cur = *s.begin();

  

    // Сохраняем первый элемент во временной переменной

    int start = cur;

  

    // Удалить первый элемент

    s.erase(s.begin());

  

    // Пройдемся, пока мультимножество не будет пустым

    while (s.size()) {

  

        // Элементы, которые на 1 больше, чем

        // текущий элемент, удалить их первое вхождение

        // и увеличиваем curr

        if (s.find(cur + 1) != s.end())

            s.erase(s.find(++cur));

  

        // Элементы, которые на 1 меньше, чем

        // текущий элемент, удалить их первое вхождение

        // и уменьшить курс

        else if (s.find(cur - 1) != s.end())

            s.erase(s.find(--cur));

  

        // Если набор не пустой и содержит элемент

        // который отличается на curr от более чем 1

        // тогда круг невозможен

        else {

            cout << "NO";

            return 0;

        }

    }

  

    // Наконец, проверяем, отличается ли curr и first на 1

    if (abs(cur - start) == 1)

        cout << "YES";

    else

        cout << "NO";

  

    return 0;

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 1, 2, 2, 2, 3 };

  

    int n = sizeof(arr) / sizeof(arr[0]);

  

    circlePossible(arr, n);

  

    return 0;

}

Выход:

YES

Рекомендуемые посты:

Проверьте, можно ли расположить элементы массива в круг с последовательной разницей в 1

0.00 (0%) 0 votes