Cho mảng A kích thước n. Hàm F(p) = mảng đã sắp xếp các tổng cặp liền kề trong p. Tìm hoán vị khác của A sao cho F(p) = F(A).
Ví dụ
Với A=[2,1,6,5,4,3], đầu ra [1,2,5,6,3,4]. Cả hai cho F = [3,7,7,9,11].
Giải thuật
Đảo ngược mảng A cho hoán vị mới. Vì tổng cặp liền kề của mảng đảo ngược là cùng một tập hợp (chỉ đổi thứ tự), sau khi sắp xếp thì giống nhau.
Mã C++
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A) {
int n = A.size();
for (int i = n - 1; i >= 0; i--)
cout << A[i] << ", ";
}
int main() {
vector<int> A = { 2, 1, 6, 5, 4, 3 };
solve(A);
}
Đầu vào / Đầu ra
Input: { 2, 1, 6, 5, 4, 3 }
Output: 3, 4, 5, 6, 1, 2,