Найдите перестановку чисел в диапазоне [L, R], имеющую пики X и долины Y

Даны целые числа L, R, X и Y такие, что (R > L ≥ 1), (X ≥ 0) и (Y ≥ 0). Найдите такую перестановку чисел в диапазоне [L, R] , что в перестановке присутствует ровно X пиков и Y впадин . Выведите Yes и перестановку, если она найдена. В противном случае напечатайте No.

Примечание. В массиве arr[] есть пик по i -му индексу, если arr[i-1] < arr[i] > arr[i+1] , и впадина по i -му индексу, если arr[i-1] > arr[i ] < arr[i+1], где 0< i < N .

Примеры:

Input: L = 1, R = 3, X = 1, Y = 0
Output: Yes, arr[] = { 1, 3, 2 }
Explanation: 1 peak is required and no valley is required. 
Clearly arr[0] < arr[1] > arr[2], arr[1] is the peak.

Input: L = 4, R = 8, X = 4, Y = 1
Output: No
Explanation: There is no such permutation of size 5 with 4 peaks and 1 valley.

Input: L = 3, R = 5, X = 0, Y = 0
Output: Yes, arr[] = { 3, 4, 5 }
Explanation: 0 peaks and 0 valleys are required. 
The sorted array has no peak or valley.

Подход: Могут быть следующие пять случаев. Следуйте подходам, указанным для каждого случая.

Случай 1 (перестановка невозможна): первый и последний элементы перестановки не влияют на количество пиков и впадин.

• Итак, если (X + Y) > (R – L – 1) , не будет перестановки, удовлетворяющей количеству пиков и впадин.
• Также, если абсолютное значение (X – Y) > 1 , такой перестановки не будет, потому что между двумя пиками ровно 1 впадина, и наоборот.

Случай 2 (X = 0, Y = 0): выполните шаги, указанные ниже.

• Создайте массив arr[] размера (R – L + 1) и сохраните числа в диапазоне [L, R] в отсортированном порядке в массиве.
• Распечатайте массив.

Случай 3 (X > Y): выполните шаги, указанные ниже:

• Создайте массив arr[] размера (R – L + 1) , состоящий из чисел в диапазоне [L, R] в отсортированном порядке.
• Рассмотрим последние (X + Y – 1) элементы, чтобы назначить X пиков и Y впадин.
• Итерируйте от i = (N – 2) до i = (N – (X + Y – 1)) . где N = (R – L + 1)
  • На каждой итерации замените arr[i] на arr[i+1] и уменьшите i на 2.
• Распечатать массив

Случай-4 (X < Y): выполните шаги, указанные ниже:

• Создайте массив arr[] размера (R – L + 1) , состоящий из чисел в диапазоне [L, R] в отсортированном порядке.
• Рассмотрим первые (X + Y) элементы, чтобы назначить X пиков и Y впадин.
• Итерация от i = 1 до i = (X+Y) .
  • Для каждой итерации замените arr[i] на arr[i-1] и увеличьте i на 2.
• Распечатайте массив.

Случай-5 (X = Y): выполните шаги, указанные ниже:

• Создайте массив arr[] длины (R – L + 1) , состоящий из чисел в диапазоне [L, R] в отсортированном порядке.
• Рассмотрим первые (X+Y) элементы, чтобы назначить (X-1) пики и Y впадины.
• Итерация от i = 1 до i = (X+Y).
  • Для каждой итерации замените arr[i] на arr[i-1] и увеличьте i на 2.
• После завершения итерации поменяйте местами последние два элемента массива, чтобы получить еще один пик.
• Распечатайте массив.

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

Временная сложность: O(N), где N = (R – L + 1)
Космическая сложность: O(1)