C++에서 최대 1개의 스왑을 사용하는 고정 소수점의 최대 수

문제 설명

0에서 N-1까지 N 요소의 순열이 주어집니다. 고정 소수점은 값이 인덱스와 같은 인덱스 즉, arr[i] =i입니다. 최대 1개의 스왑을 수행할 수 있습니다. 얻을 수 있는 최대 고정 포인트 수를 찾으십시오.

예

입력 배열이 {0, 1, 2, 3, 4, 6, 5}이면 답은 7입니다.

• 고정 소수점을 조정하려면 6과 5를 바꿔야 합니다.
• 이 전체 배열이 고정 소수점이 되고 고정 소수점의 최대값은 7이 됩니다.

알고리즘

• 입력 배열에서 각 요소의 위치를 ​​유지하는 배열 pos 생성
• 이제 배열을 탐색하고 다음과 같은 경우가 있습니다. -
  • 만약, a[i] =i. 카운트를 늘리고 계속 진행할 수 있습니다.
  • If, pos[i] =a[i] 즉, 2개의 항을 교환하면 i와 a[i]가 고정 소수점이 되어 개수가 2 증가합니다. 교환은 최대 한 번만 수행될 수 있다는 점에 유의하십시오. .
• 순회가 끝날 때 스왑을 수행하지 않았다면 스왑이 카운트를 2만큼 늘릴 수 없었음을 의미하므로 이제 고정 소수점이 아닌 요소가 2개 이상 있으면 다음을 수행할 수 있습니다. 스왑을 수행하여 개수를 1만큼 늘리십시오. 즉, 해당 지점 중 하나를 고정 지점으로 만듭니다.

예

#include <bits/stdc++.h>
using namespace std;
int getMaximumFixedPoints(int arr[], int n) {
   int i, pos[n], count = 0, swapped = 0;
   for (i = 0; i < n; i++)
   pos[arr[i]] = i;
   for (i = 0; i < n; i++) {
      if (arr[i] == i) {
         count++;
      } else if (swapped == 0 && pos[i] == arr[i]) {
         count += 2;
         swapped = 1;
      }
   }
   if (swapped == 0 && count < n - 1) {
      count++;
   }
   return count;
}
int main() {
   int arr[] = {0, 1, 2, 3, 4, 6, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Maximum edges = 7