写一段c++代码You are given an unsorted permutation p_1, p_2, \ldots, p_np 1 ,p 2 ,…,p n . To sort the permutation, you choose a constant kk (k \ge 1k≥1) and do some operations on the permutation. In one operation, you can choose two integers ii, jj (1 \le j < i \le n1≤j<i≤n) such that i - j = ki−j=k, then swap p_ip i and p_jp j . What is the maximum value of kk that you can choose to sort the given permutation? A permutation is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2, 3, 1, 5, 4][2,3,1,5,4] is a permutation, but [1, 2, 2][1,2,2] is not a permutation (22 appears twice in the array) and [1, 3, 4][1,3,4] is also not a permutation (n = 3n=3 but there is 44 in the array). An unsorted permutation pp is a permutation such that there is at least one position ii that satisfies p_i \ne ip i =i.
时间: 2023-12-16 10:04:12 浏览: 96
Here's the C++ code to solve the problem:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
int max_k = n / 2; // maximum value of k
for (int k = max_k; k >= 1; k--) {
for (int i = 0; i < k; i++) { // sort each k-length block separately
for (int j = i+k; j < n; j += k) {
if (p[j] < p[j-k]) {
swap(p[j], p[j-k]);
}
}
}
if (is_sorted(p.begin(), p.end())) { // check if the permutation is sorted
cout << k << endl;
break;
}
}
return 0;
}
```
The code reads in the input permutation, then iterates over the possible values of k in descending order from n/2 to 1. For each value of k, it sorts each k-length block separately using a simple bubble sort, and checks if the entire permutation is sorted. If it is, then it outputs the value of k and exits. If no value of k sorts the permutation, then it outputs -1.
阅读全文