n個のピークを持つ順列を見つけるC++プログラム

nとkの2つの数があるとします。正確にk個のピークを持つ1からnまでの数を使用して順列Aを構築する必要があります。 A [i]>A[i-1]およびA[i]>A [i + 1]の場合、インデックスiは配列Aのピークであると言われます。これが不可能な場合は、-1を返します。

したがって、入力がn=5のような場合。 k =2の場合、出力は[2、4、1、5、3]になり、他の回答も可能です。

ステップ

これを解決するには、次の手順に従います-

if k > (n - 1) / 2, then:
   return -1
Define an array a of size: 101.
for initialize i := 1, when i <= n, update (increase i by 1), do:
   a[i] := i
for initialize i := 2, when i <= 2 * k, update i := i + 2, do:
   swap a[i] and a[i + 1]
for initialize i := 1, when i <= n, update (increase i by 1), do:
   print a[i]

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int k) {
   if (k > (n - 1) / 2) {
      cout << "-1";
      return;
   }
   int a[101];
   for (int i = 1; i <= n; i++)
      a[i] = i;
   for (int i = 2; i <= 2 * k; i += 2) {
      swap(a[i], a[i + 1]);
   }
   for (int i = 1; i <= n; i++)
      cout << a[i] << ", ";
}
int main() {
   int n = 5;
   int k = 2;
   solve(n, k);
}

入力

5, 2

出力

1, 3, 2, 5, 4,