Atcoder Beginner Contest 350 C - Sort

Atcoder Beginner Contest 350

Contest Duration: 2024-04-20(Sat) 20:00 - 2024-04-20(Sat) 21:40 (local time) (100 minutes)

C - Sort

Problem Statement

You are given a permutation A=(A 1 ​ ,…,A N ​ ) of (1,2,…,N). Transform A into (1,2,…,N) by performing the following operation between 0 and N−1 times, inclusive: Operation: Choose any pair of integers (i,j) such that 1≤i<j≤N. Swap the elements at the i-th and j-th positions of A. It can be proved that under the given constraints, it is always possible to transform A into (1,2,…,N).

翻译

给定一个排列 A=(A1, ..., AN) ，其中包含数字 1 到 N 的一个排列。通过执行 0 到 N-1 次操作，将排列 A 转换为 (1, 2, ..., N)。每次操作如下：选择任意一对整数 (i, j)，其中 1≤i<j≤N，在排列 A 中交换第 i 个位置和第 j 个位置上的元素。在给定的约束条件下，可以证明始终可以将排列 A 转换为 (1, 2, ..., N)。

思路

通过从开头迭代元素并将每个元素与正确位置上的元素交换，最多可以通过 (N-1) 次操作实现目标。

如果在这个过程中每次都尝试查找元素 i 在数组 A 中的当前位置，那么在最坏情况下，每次查找都会耗费 O(N) 的时间，总共将会耗费 O(N^2) 的时间，导致超时（Time Limit Exceeded）的结果。

相反，除了数组 A 外，还要维护另一个数组 pos，用于表示值 i 在数组 A 中的位置，并相应地更新它。例如，如果 A=(3,1,2,4)，则 pos=(2,3,1,4)。 这样，可以在 O(1) 的时间内引用数组 A 中元素 i 的当前位置，总共需要 O(N) 的时间来解决整个问题。

来看看C知道写的代码（可能TLE）：

这个问题的目标是将给定的排列A转换为(1,2,…,N)。转换操作是选择任意一对整数(i,j)，其中1≤i<j≤N，然后交换A中第i个和第j个位置上的元素。根据给定的约束条件，可以证明总是可以将A转换为(1,2,…,N)。

输入格式为：N A1 A2 … AN，其中N表示排列的长度，A1到AN表示排列中的元素。

输出格式为：K+1行，第一行包含K，表示操作的次数。接下来的K行中，每行包含一个操作所选择的i和j，用空格分隔。

以下是一个C++代码及题解的示例：

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int N;
    cin >> N;
    
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    vector<pair<int, int>> operations;
    
    // Perform the necessary operations to transform A into (1,2,...,N)
    for (int i = 0; i < N; i++) {
        if (A[i] != i + 1) {
            int j = i + 1;
            while (A[j - 1] != i + 1) {
                j++;
            }
            operations.push_back(make_pair(i + 1, j));
            swap(A[i], A[j - 1]);
        }
    }
    
    int K = operations.size();
    
    cout << K << endl;
    for (int i = 0; i < K; i++) {
        cout << operations[i].first << " " << operations[i].second << endl;
    }
    
    return 0;
}

另一个解法：

C - Sort
置换环，有两种写法

1.
对于错位的元素，可以将应该在该位置的元素调换过来，这种写法就需要两个数组互相映射，比较绕，不推荐写这种。

2.
对于错位的元素，可以选择将该元素替换至它应该在的地方，每次替换都至少能让一个元素归位，所以最多也是 n − 1 n-1n−1 次就可以有序。写起来更方便，只需要一个数组维护此时各个元素的位置，然后每次while当前元素错位，交换即可，代码：

#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
int arr[maxn], pos[maxn];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    vector<pii> ans;
    for (int i = 1; i <= n; i++) {
        while (arr[i] != i) {
            ans.push_back(pii(i, arr[i]));
            swap(arr[i], arr[arr[i]]);
        }
    }
    cout << ans.size() << endl;
    for (auto [u, v] : ans)
        cout << u << " " << v << endl;
    // system("pause");
    return 0;
}

另一种解法：

#include <iostream>
#include <queue>
using namespace std;
int n;
int a[200100];
int p = -1;
int idx[200100];
queue<pair<int, int>> q;
 
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		idx[a[i]] = i;
	}
	int cnt = 0;
	
	for (int i = 1; i <= n; i++) {
		if (a[i] != i) {
			cnt++;
			q.push({min(idx[i], i), max(idx[i], i)});
			int tmp = idx[i];
			swap(idx[a[i]], idx[i]);
			swap(a[i], a[tmp]);
			
		}
	}
	cout << cnt << '\n';
	while (!q.empty()) {
		cout << q.front().first << ' ' << q.front().second << '\n';
		q.pop();
	}
	return 0;
}